Trees Field Notes

0Why trees exist

A linked list is a chain: one node, then the next, then the next. A tree is the same idea, nodes and pointers, but each node can point to more than one node below it. That single change gives you a hierarchy (levels of parents and children), and, when the values are kept in order, a structure you can search in O(log n) while still inserting and deleting in O(log n). A sorted array cannot do the second part.

Six lessons, one page. Lesson 16 is vocabulary. Lesson 17 adds the sorted rule (a BST). Lesson 18 changes the tree. Lessons 19 and 20 walk the whole tree in two different orders. Lesson 21 uses a BST to build a sorted set and a sorted map.

1Binary trees

The node: one value, two pointers

Like linked lists, binary trees are built from nodes and pointers. A linked list node points to the next node. A binary tree node has at most two pointers, called the left child and the right child. The first node, the one at the top, is the root. NeetCode draws the pointers going downward, and so does every diagram here.

class ListNode:                 # from the linked list lessons
    def __init__(self, val):
        self.val = val
        self.next = None

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

Building a tree by hand

Create the nodes, then attach them. This is the tree NeetCode uses for the BST search lesson: root 2, left child 1, right child 3, and 4 under 3 on the right.

root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)
root.right.right = TreeNode(4)    # 4 is the right child of 3

LeetCode and NeetCode describe a tree as a list, level by level, left to right, with null for a missing child. This tree is [2,1,3,null,null,null,4]: level 1 is 2; level 2 is 1, 3; level 3 is the children of 1 (null, null) then the children of 3 (null, 4). Trailing nulls are dropped. A small helper turns that list into real nodes so you can test locally.

from collections import deque

def build_tree(values):
    """[2,1,3,None,None,None,4] -> root of that tree (LeetCode format)."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

Leaves, and why one always exists

A node with no children is a leaf. A node with even one child, left or right, is a non-leaf node. Unlike a linked list, tree pointers go only one way, down, and cycles are not allowed. Mathematically a binary tree is a connected, undirected graph with no cycles: every node is reachable, and there is no way to walk back to where you started. Because there are no cycles, walking down must end somewhere, so a leaf node is always guaranteed to exist.

The words interviewers use

Lesson 16 is mostly definitions, but every tree question is asked in these words, so they must be automatic.

• Root node: the highest node; it has no parent, and every node is reachable from it.
• Leaf nodes: nodes with no children. Nodes on the last level are guaranteed to be leaves, but leaves can sit on other levels too (node 1 above).
• Children: a node's left child and right child.
• Height: measured from the root down to the lowest leaf. A single-node tree has height 1 if you count nodes, or 0 if you count edges. When counting edges, height = n - 1 where n is the number of nodes on the path from the root to the lowest leaf. Ask which one a problem wants; LeetCode 104 counts nodes.
• Depth: measured from a node up to the root. The root has depth 1, and depth grows as you go down. Depth of a node = how many nodes are above it, itself included.
• Ancestor: a node connected to all the nodes below it. The root is an ancestor of every node.
• Descendant: a child of the node, or a child of some other descendant of the node. Everything below.
• Number of edges: always n - 1 for n nodes, because every node except the root has exactly one pointer coming into it.

def height_nodes(root):             # count nodes on the longest path
    if not root:
        return 0
    return 1 + max(height_nodes(root.left), height_nodes(root.right))

def height_edges(root):             # count edges: one less than nodes
    if not root:
        return -1                     # so a single node gives 1 + (-1) = 0
    return 1 + max(height_edges(root.left), height_edges(root.right))

def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

# for [2,1,3,None,None,None,4]:  height_nodes = 3,  height_edges = 2,
#                                 count_nodes = 4,  edges = 4 - 1 = 3

2Binary search trees

Binary tree vs BST

A binary search tree (BST) is a binary tree with a sorted property: every node in the left subtree is smaller than the root, and every node in the right subtree is greater than the root. The property is recursive: it applies at every node, not only at the top. Node 6 below has 5 on its left and 7 on its right, for the same reason. A BST is the tree version of a sorted array.

Why a BST instead of a sorted array?

Both give you search in O(log n). The difference is what happens when the data changes. Inserting into a sorted array means shifting everything after the new spot, O(n). Inserting into a balanced BST is a walk down the tree plus one pointer change, O(log n). Same for deletion. So BSTs are often preferred when you must search and keep adding and removing.

BST search

Trees are recursive (a subtree is a smaller tree), so we search with recursion. The tree is [2,1,3,null,null,null,4] and the target is 3. Same idea as binary search: target smaller than the current node, go left; target bigger, go right. Reach the target node: return True. Reach None: return False.

def search(root, target):
    if not root:
        return False

    if target > root.val:
        return search(root.right, target)
    elif target < root.val:
        return search(root.left, target)
    else:
        return True

1. None node: return False. The target is not in this subtree. Base case.
2. Target greater than the current value: search the right subtree.
3. Target smaller than the current value: search the left subtree.
4. Target equals the current value: return True. Base case.

In steps 2 and 3 the recursive call's return value is the current call's return value. There is nothing to do after the call returns, so you write return search(...) and let the answer flow straight back up.

The same walk without recursion. Interviewers like this version because it uses no call stack.

def search_iter(root, target):
    cur = root
    while cur:
        if target > cur.val:
            cur = cur.right
        elif target < cur.val:
            cur = cur.left
        else:
            return True
    return False

Time: O(log n) if balanced, O(n) if skewed

A tree is balanced when, at every node, the height of the left subtree equals the height of the right subtree, or differs by 1. In a balanced tree each comparison throws away about half of the remaining nodes, exactly the reasoning from binary search and merge sort, so search takes O(log n) steps.

The worst case is a skewed tree, where every node has only one child and the height equals the number of nodes. Then the search walks a straight line: O(n). A skewed tree is a linked list wearing a tree costume.

3Insert and remove in a BST

The main benefit of a BST over a sorted array is here: insertion and removal in O(log n), assuming the tree is balanced. Both are "search for the spot, then change one or two pointers".

Insertion: walk down, attach a leaf

Traverse to find the right position, then insert while keeping the sorted property. Start with the BST [4] and insert 6. Two results are valid: [4,null,6] (6 as the right child of 4) or [6,4,null] (6 as the new root with 4 on its left). The first one adds 6 as a leaf, which is easier, and it is what the code does. Then insert 5 into [4,null,6]: 5 is bigger than 4, so go right; 5 is smaller than 6, so go left; that spot is empty, so 5 becomes the left child of 6, giving [4,null,6,5,null].

# Insert a new node and return the root of the BST.
def insert(root, val):
    if not root:
        return TreeNode(val)

    if val > root.val:
        root.right = insert(root.right, val)
    elif val < root.val:
        root.left = insert(root.left, val)
    return root

• Current node is None: return a brand new node holding val. This is the line that adds the node.
• val greater than the current value: recurse on the right child. Smaller: recurse on the left child.
• Return the current node after the recursive call. The return value of each recursive call is assigned to root.left or root.right. That assignment is how the tree structure is maintained: the parent re-attaches whatever the child call hands back, which is either the same child or a brand new node.

Time is O(log n) when balanced: we walk until we reach a leaf, so the number of visited nodes is proportional to the height. Equal values are ignored by this code (neither branch fires, the node is returned unchanged), which is what a set wants. NeetCode's video: "6 is greater than the root 4, so it goes in the right subtree. 5 is greater than 4 but less than 6, so it goes in the left subtree of the tree rooted at 6."

Removal: two cases

Removing is harder because the node may have children that must stay in the tree. Count the target's children.

Case 1: the target has 0 or 1 child. Delete node 2, which has no children: the left pointer of 3 now points to None. Delete node 3, which has one child: the left pointer of the root now points to 2 instead of 3. The child moves up into the hole. Nothing else changes.

Case 2: the target has 2 children. Delete node 6. You cannot point 4 at both 5 and 7. Instead, replace 6 with its in-order successor: the left-most node in the right subtree of the target, which is the smallest node among all nodes greater than the target. Here that is 7. Copy 7 into the target node, then remove the original 7 from the right subtree (it is a leaf, so that is case 1). Every node left of the new 7 is smaller than it and every node right of it is bigger, so the tree stays a valid BST.

# Return the minimum value node of the BST.
def minValueNode(root):
    curr = root
    while curr and curr.left:
        curr = curr.left
    return curr

# Remove a node and return the root of the BST.
def remove(root, val):
    if not root:
        return None

    if val > root.val:
        root.right = remove(root.right, val)
    elif val < root.val:
        root.left = remove(root.left, val)
    else:                                       # found the node to delete
        if not root.left:
            return root.right                   # 0 or 1 child: hand the other side up
        elif not root.right:
            return root.left
        else:                                   # 2 children
            minNode = minValueNode(root.right)   # in-order successor
            root.val = minNode.val               # copy it up
            root.right = remove(root.right, minNode.val)   # delete the copy below
    return root

Read the middle branch slowly. if not root.left: return root.right covers two situations at once: no children at all (then root.right is None, and the parent's pointer becomes None), and only a right child (the parent's pointer becomes that child). The parent re-attaches whatever is returned, the same trick as in insert.

Time and space

Time is proportional to the height, essentially a binary search down the tree: O(log n) balanced, O(n) worst case (unbalanced). Space is the recursion: the number of recursive calls on the stack is also proportional to the height, so O(log n) best, O(n) worst.

4Depth-first search

DFS is one of the most common interview algorithms. It is used to traverse trees and graphs; here, trees. To traverse an entire tree we must visit every node. DFS picks a direction, say left, and keeps following pointers as far down-left as possible until it hits None. Then it backtracks (returns to the parent) and goes right. Repeat until every node has been visited. "Go as deep as possible before backtracking."

There are three DFS orders, named after when the parent is visited relative to its children: inorder, preorder, postorder. All three are best written with recursion; each can also be written with an explicit stack (section 7). The tree for this lesson is [4,3,6,2,null,5,7]: root 4, left child 3 with left child 2, right child 6 with children 5 and 7.

Inorder: left subtree, then the node, then right subtree

def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

Visit order: [2, 3, 4, 5, 6, 7], which is sorted. Inorder prints sorted order only if the tree is a BST. All values to the left are smaller, so we hit the base case at the left-most (smallest) node first, print it, then its parent, then the parent's right subtree, and so on. Run the same function on a non-BST with the same shape, like [1,2,3], and you get [2, 1, 3].

Preorder: the node first, then left subtree, then right subtree

def preorder(root):
    if not root:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

Visit order: [4, 3, 2, 6, 5, 7]. The root always comes out first. Preorder is the order you would use to copy a tree or serialize it, because you see each parent before its children.

Postorder: left subtree, right subtree, the node last

def postorder(root):
    if not root:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

Visit order: [2, 3, 5, 7, 6, 4]. The root always comes out last. Postorder is the order for "finish the children, then use their results", such as computing a height or deleting a tree from the bottom.

Time and space (all three)

Time O(n): every node is visited exactly once, regardless of the height. Note: an inorder traversal of a BST builds a sorted array, which is the cheap way to get "all values in order" out of a BST. Space O(h) where h is the height, because that is how deep the call stack gets: O(log n) for a balanced tree, O(n) for a skewed one.

5Breadth-first search

DFS prioritizes depth. BFS prioritizes breadth: visit all nodes on one level before moving to the next. For trees BFS is also called level-order traversal.

Implementation: a queue, level by level

BFS is written iteratively. We need a data structure that lets us finish a whole level before starting the next. That is a queue, specifically a deque, because it removes from the head and appends to the tail in O(1). Append children to the tail, remove parents from the head, and each level comes out left to right.

from collections import deque

def bfs(root):
    queue = deque()

    if root:
        queue.append(root)

    level = 0
    while len(queue) > 0:
        print("level: ", level)
        for i in range(len(queue)):        # exactly the nodes of this level
            curr = queue.popleft()
            print(curr.val)
            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)
        level += 1

1. Append the root to the queue (if there is one).
2. While the queue is not empty: print the level number.
3. Loop len(queue) times. That number is the size of the current level, and it is read once, before the loop starts, so children appended during the loop are not counted as part of this level.
4. For each removed node, append its children, left then right.
5. After the level is done, level += 1.
6. The queue empties when every node has been visited, and the while loop ends.

Time and space

Time O(n): each node is added to the queue once and removed once. Space O(n): the queue holds an entire level at a time, and in a full tree the last level holds roughly half of all nodes. Compare with DFS, whose stack holds one root-to-leaf path, O(h).

6BST sets and maps

Sets and maps, like stacks and queues, are interfaces: a list of operations, not a fixed way of storing things. One way to implement them is with a tree, and then insertion, deletion, and search all run in O(log n).

Sets

A phone book with the names Alice, Brad, Collin. A set ensures unique values: adding "Alice" twice keeps one Alice. Implementing it with a BST also keeps the keys sorted (alphabetically here), because inorder traversal gives sorted order. This is a TreeSet.

Maps

A map works on key-value pairs. Built with a tree it is a TreeMap. The phone book maps names to phone numbers, sorted by key: {'Alice': 123, 'Brad': 345, 'Collin': 678}. The key could be the last name; the value can be a number, an object, any type. The only requirement is that keys must be comparable, because the tree needs an order to decide left or right. TreeMap operations run in O(log n).

Here is a small TreeMap written on top of the insert and search you already know. Keys stay unique because equal keys overwrite the value instead of adding a node.

class TreeMap:
    class Node:
        def __init__(self, key, value):
            self.key, self.value = key, value
            self.left = self.right = None

    def __init__(self):
        self.root = None

    def put(self, key, value):
        def ins(node):
            if not node:
                return TreeMap.Node(key, value)
            if key < node.key:
                node.left = ins(node.left)
            elif key > node.key:
                node.right = ins(node.right)
            else:
                node.value = value          # same key: overwrite, keys stay unique
            return node
        self.root = ins(self.root)

    def get(self, key):
        cur = self.root
        while cur:
            if key < cur.key:
                cur = cur.left
            elif key > cur.key:
                cur = cur.right
            else:
                return cur.value
        return None

    def items(self):                        # inorder = sorted by key
        out = []
        def walk(node):
            if not node:
                return
            walk(node.left)
            out.append((node.key, node.value))
            walk(node.right)
        walk(self.root)
        return out

phone = TreeMap()
phone.put("Collin", 678)
phone.put("Alice", 123)
phone.put("Brad", 345)
phone.get("Brad")      # 345
phone.items()          # [('Alice', 123), ('Brad', 345), ('Collin', 678)]

In different languages

Java and C++ ship a TreeMap in the standard library. Python and JavaScript do not; you install one.

# Python: pip install sortedcontainers
from sortedcontainers import SortedDict
treemap = SortedDict({'c': 3, 'a': 1, 'b': 2})
list(treemap.keys())    # ['a', 'b', 'c']  - always sorted

# Java:        TreeMap treeMap = new TreeMap();
# JavaScript:  const TreeMap = require("treemap-js"); let map = new TreeMap();
# C++:         map<string, string> treeMap;

sortedcontainers also gives you SortedList (a sorted list with O(log n) insert, index, and bisect_left) and SortedSet (the TreeSet). Internally they are not trees but lists of lists; the interface and the Big-O are what matter in an interview.

7Moves that solve most tree problems

The lessons teach the structure and the traversals. Interview questions are those traversals with a small twist. Learn these five moves.

Move 1: the recursive template, "combine(left, right)"

Almost every tree function has this shape: handle None, ask both children, combine their two answers with the current node, return one value. Height, node count, sum, maximum path, "is it the same tree", "invert it" all fit.

def solve(root):
    if not root:
        return base            # 0, True, None, ... whatever an empty tree answers
    left = solve(root.left)
    right = solve(root.right)
    return combine(left, right, root)

def max_depth(root):                 # LeetCode 104 (counts nodes)
    if not root:
        return 0
    left = max_depth(root.left)
    right = max_depth(root.right)
    return 1 + max(left, right)

def invert(root):                    # LeetCode 226: swap every left and right
    if not root:
        return None
    root.left, root.right = invert(root.right), invert(root.left)
    return root

def same_tree(p, q):                 # LeetCode 100: two trees at once
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return same_tree(p.left, q.left) and same_tree(p.right, q.right)

When the answer is not the same thing the function returns, keep a side variable. Diameter (longest path, in edges) and "is balanced" both return a height upward while recording something else.

def diameter(root):                  # LeetCode 543
    best = 0

    def height(node):
        nonlocal best
        if not node:
            return 0
        l = height(node.left)
        r = height(node.right)
        best = max(best, l + r)      # longest path THROUGH this node, in edges
        return 1 + max(l, r)         # but hand the height upward

    height(root)
    return best

def is_balanced(root):               # LeetCode 110
    def check(node):                 # returns height, or -1 if anything below is unbalanced
        if not node:
            return 0
        l = check(node.left)
        if l == -1:
            return -1
        r = check(node.right)
        if r == -1:
            return -1
        if abs(l - r) > 1:
            return -1
        return 1 + max(l, r)

    return check(root) != -1

Move 2: DFS with an explicit stack

Same order as the recursive version, but you manage the stack yourself. Preorder is the easy one: pop a node, visit it, push right then left so that left is popped first. Inorder needs a "slide down-left, then pop, then step right" loop.

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:                 # push right first so left is popped first
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out                         # [4, 3, 2, 6, 5, 7]

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                     # slide down-left, remembering the path
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()              # nothing further left: visit
        out.append(cur.val)
        cur = cur.right                # then go right
    return out                         # [2, 3, 4, 5, 6, 7]

The inorder stack version is also the tool for kth smallest in a BST: stop after k pops.

def kth_smallest(root, k):           # LeetCode 230
    stack, cur = [], root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        k -= 1
        if k == 0:
            return cur.val
        cur = cur.right

Move 3: BFS with the level-size loop

The lesson's bfs prints. Interview versions return a list per level. Freeze size = len(queue) before the inner loop; that number is the whole trick.

def level_order(root):               # LeetCode 102
    levels = []
    queue = deque([root] if root else [])
    while queue:
        size = len(queue)              # freeze the size: only this level
        level = []
        for _ in range(size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels                      # [[4], [3, 6], [2, 5, 7]]

def right_side_view(root):           # LeetCode 199: last node of every level
    return [level[-1] for level in level_order(root)]

Move 4: validate a BST with min / max bounds

The trap: checking only left.val < node.val < right.val at each node is not enough. In [5,4,7,null,6], node 6 is a valid right child of 4, but it sits in the left subtree of 5, where everything must be below 5. Carry a range down instead: every node must be strictly between low and high, and each step narrows one side.

def is_valid_bst(root, low=float("-inf"), high=float("inf")):   # LeetCode 98
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

Move 5: use the BST order to prune

On a BST, do not visit both children. Compare and go one way, like search. Lowest common ancestor is the classic: the first node where the two targets split to different sides (or one of them equals the node) is the answer.

def lca_bst(root, p, q):             # LeetCode 235, p and q are values
    cur = root
    while cur:
        if p < cur.val and q < cur.val:
            cur = cur.left
        elif p > cur.val and q > cur.val:
            cur = cur.right
        else:
            return cur.val               # they split here (or one is here)

8Big-O summary

Say the word "balanced" every time you say O(log n). h is the height: about log n for a balanced tree, up to n for a skewed one.

The hash map star means "average case"; hashing is a later topic. BFS space is O(n) on a balanced tree because the last level of a full tree holds about n/2 nodes; on a skewed tree each level has one node, so the queue never grows, which is the one place a skewed tree wins. DFS space is the opposite: it holds one root-to-leaf path, which is short on a balanced tree and the whole tree on a skewed one.

9Mistakes to watch for

10Practice, in this order

Do these on LeetCode with the notes closed. The first five are the recursive template with different combine steps; do not move on until they feel like one problem.

Your next step today: LeetCode 104. Write it from memory, then draw the return value next to every node of [4,3,6,2,null,5,7] and check that the root gets 3.

11Self-check

Answer out loud before opening. If you cannot answer in one breath, reread that section.