Know this before you start: “Height, depth, and BST properties”

Height, depth and binary search trees

Depth counts edges down from the root, height counts the longest path down to a leaf. In a BST, everything left is smaller and everything right is bigger.

The idea

A node's depth is how far it is from the root; a tree's height is the longest root-to-leaf path. Height has a neat recursion: 1 + the taller child's height, with an empty tree at 0.

A binary search tree adds a rule for every node: all values in the left subtree are smaller, all in the right are bigger. So searching goes left or right at each node, O(h), and an inorder walk lists the values sorted.

To check a BST, pass down the allowed range (low, high): checking only a node against its children isn't enough.

See it step by step

Is 5 → (1, 4 → (3, 6)) a BST?

Root 5: its right subtree must be > 5.
4 is in the right subtree but 4 < 5 → not a BST, even though 4's own children (3 < 4 < 6) look fine.
That's why the allowed range is passed down.

In code (Python)

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def height(node):
    if not node:
        return 0
    return 1 + max(height(node.left), height(node.right))

def is_bst(node, low=float("-inf"), high=float("inf")):
    if not node:
        return True
    if not low < node.val < high:
        return False
    return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)

good = TreeNode(2, TreeNode(1), TreeNode(3))
bad = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
print(height(good), is_bst(good), is_bst(bad))   # 2 True False

Height and BST check: O(n). BST search: O(h), which is O(log n) when balanced.

When you'll use it

Maximum / minimum depth, balanced tree, diameter, validate BST, k-th smallest, lowest common ancestor in a BST.

Common mistakes

Validating a BST by comparing only parent and children.
Mixing up depth (from the top) and height (to the bottom).