Trees

1. Anatomy of a Tree

      A  (Root)
     /|\
    B C D  (Children of A)
   / \   |
  E   F  G  (Leaf Nodes)

Understanding the terminology is the first step:

• Node: The basic unit of a tree, containing a value and pointers to its children. (e.g., A, B, C...)
• Root: The topmost node of the tree. A tree has only one root. (e.g., A)
• Edge: The link or pointer between two nodes. (e.g., the line connecting A and B)
• Parent & Child: A node that points to other nodes is a parent; the nodes it points to are its children. (e.g., A is the parent of B, C, and D)
• Leaf: A node with no children. (e.g., E, F, G)
• Height: The length of the longest path (number of edges) from a node to a leaf. The height of the tree is the height of its root.
• Depth: The length of the path from the root to a specific node. The depth of the root is 0.

2. Binary Trees

      F (Root)
     / \
    B   G
   / \   \
  A   D   I (Right Child of G)
     / \
    C   E

A Binary Tree is a specific type of tree where each node can have at most two children: a left child and a right child. This simple constraint leads to a huge variety of useful applications and algorithms.

Node Implementation

Here’s how a simple tree node is typically defined in different languages:

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

3. Tree Traversal

Traversal is the process of visiting (checking or updating) each node in a tree exactly once. The order in which nodes are visited defines the traversal type.

      F
     / \
    B   G
   / \   \
  A   D   I
     / \ /
    C  E H

Depth-First Search (DFS)

DFS explores as far as possible down each branch before backtracking. It's naturally implemented with recursion (which uses the call stack implicitly).

• Preorder (Root, Left, Right): Visits the current node first, then recursively visits the left subtree, then the right subtree. Useful for creating a copy of a tree.
  Sample Output: F, B, A, D, C, E, G, I, H
• Inorder (Left, Root, Right): Recursively visits the left subtree, then the current node, then the right subtree. For a Binary Search Tree, this traversal visits nodes in sorted order.
  Sample Output: A, B, C, D, E, F, G, H, I
• Postorder (Left, Right, Root): Recursively visits the left subtree, then the right subtree, then the current node. Useful for deleting nodes, as you can delete a node after processing its children.
  Sample Output: A, C, E, D, B, H, I, G, F

Breadth-First Search (BFS) / Level Order Traversal

BFS explores the tree layer by layer, visiting all nodes at the current depth before moving on to the next level. It is implemented iteratively using a Queue.

4. Classic Problems

Maximum Depth of a Binary Tree

A classic recursive problem. The depth of a tree is 1 plus the maximum depth of its left and right subtrees.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        return 1 + max(left_depth, right_depth)

Invert Binary Tree

Swap the left and right children of every node in the tree. This is a perfect example of a recursive postorder traversal problem.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        # Swap the children
        root.left, root.right = root.right, root.left
        
        # Recurse on the (new) left and right subtrees
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root

Validate Binary Search Tree

A common interview question with a tricky edge case. It's not enough to check that node.left.val < node.val < node.right.val. You must validate that all nodes in the left subtree are less than the node's value, and all in the right are greater. This is done by passing down valid range constraints (min and max) during the traversal.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, low=-float('inf'), high=float('inf')):
            if not node:
                return True
            if not (low < node.val < high):
                return False
            
            return (validate(node.left, low, node.val) and
                    validate(node.right, node.val, high))
        
        return validate(root)

Lowest Common Ancestor of a BST

The Lowest Common Ancestor (LCA) is the deepest node that has both given nodes as descendants. In a BST, you can find the LCA efficiently by exploiting its sorted property.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        curr = root
        while curr:
            if p.val > curr.val and q.val > curr.val:
                curr = curr.right
            elif p.val < curr.val and q.val < curr.val:
                curr = curr.left
            else:
                return curr