Binary Trees

What is a Binary Tree?

• Each node has at most 2 children
• Root: top node (no parent)
• Leaf: node with no children

      1
     / \
    2   3
   / \
  4   5

The Recursion Pattern

func solve(root *TreeNode) Result {
    if root == nil {
        return baseValue
    }
    left := solve(root.Left)
    right := solve(root.Right)
    return combine(root.Val, left, right)
}

Think: what do I need from children?

Maximum Depth

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(
        maxDepth(root.Left),
        maxDepth(root.Right),
    )
}

"My depth = 1 + deeper child"

Invert a Tree

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

Swap at every node.

BST Property

Left subtree < Node < Right subtree

      5
     / \
    3   7
   / \
  1   4

Inorder traversal = sorted order

Validate BST

Pass valid range down:

func validate(node, min, max) bool {
    if node == nil { return true }
    if node.Val <= min || node.Val >= max {
        return false
    }
    return validate(node.Left, min, node.Val) &&
           validate(node.Right, node.Val, max)
}

Lowest Common Ancestor

func LCA(root, p, q) *TreeNode {
    if root == nil || root == p || root == q {
        return root
    }
    left := LCA(root.Left, p, q)
    right := LCA(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil { return left }
    return right
}

Complexity

h = height (log n balanced, n skewed)