Overview

  • A tree is a hierarchical data structure consisting of nodes, where each node has a value and a list of child nodes.
  • The topmost node is called the root.
  • Nodes with no children are called leaves.
  • Trees are commonly used to represent hierarchical relationships and structures.

Key Terminology

  • Root: The topmost node in a tree.
  • Parent: A node that has child nodes.
  • Child: A node that has a parent node.
  • Leaf: A node with no children.
  • Height of Tree: The number of edges on the longest path from the root to a leaf.
  • Depth of Node: The number of edges from the root to the node.
  • Binary Tree: A tree where each node has at most two children.
  • Binary Search Tree (BST): A binary tree where the left child’s value is less than the parent’s value, and the right child’s value is greater than the parent’s value.

Tree Traversal Methods

Traversal refers to visiting all the nodes in a tree in a specific order.

1. Depth-First Search (DFS)

DFS explores as far as possible along a branch before backtracking.

  • Inorder Traversal (Left, Root, Right)
  • Preorder Traversal (Root, Left, Right)
  • Postorder Traversal (Left, Right, Root)
# Example: Inorder Traversal (Recursive)
def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

# Example: Preorder Traversal (Iterative)
def preorder_traversal(root):
    stack, result = [root], []
    while stack:
        node = stack.pop()
        if node:
            result.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
    return result

2. Breadth-First Search (BFS)

BFS explores all nodes at the current depth level before moving on to nodes at the next depth level.

  • Implemented using a queue.
# Example: Level Order Traversal
def level_order_traversal(root):
    if not root:
        return []
    from collections import deque
    queue, result = deque([root]), []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Common Tree Types

1. Binary Tree

  • A tree where each node has at most two children.

2. Binary Search Tree (BST)

  • A binary tree with the property: left subtree < root < right subtree.
  • Used for fast lookup, insertion, and deletion (O(log n) on average).
# Example: Search in BST
def search_bst(root, val):
    if not root or root.val == val:
        return root
    return search_bst(root.left, val) if val < root.val else search_bst(root.right, val)

3. Balanced Binary Tree

  • A binary tree where the height difference between left and right subtrees is at most 1.

4. Complete Binary Tree

  • A binary tree where all levels are completely filled except possibly the last, which is filled from left to right.

5. N-ary Tree

  • A tree where nodes can have at most N children.

6. Trie (Prefix Tree)

  • A tree used to store strings where each node represents a character.

Common Tree Problems

1. Maximum Depth of Binary Tree

Find the height of the tree.

# Example: Maximum Depth
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

2. Validate Binary Search Tree

Check if a binary tree is a valid BST.

# Example: Validate BST
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    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)

3. Lowest Common Ancestor (LCA)

Find the lowest common ancestor of two nodes.

# Example: LCA in Binary Tree
def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    return root if left and right else left or right

4. Diameter of Binary Tree

Find the longest path between any two nodes.

# Example: Diameter of Binary Tree
def diameter_of_binary_tree(root):
    def dfs(node):
        nonlocal diameter
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        diameter = max(diameter, left + right)
        return 1 + max(left, right)

    diameter = 0
    dfs(root)
    return diameter

5. Serialize and Deserialize Binary Tree

Convert a tree into a string and back.

# Example: Serialize and Deserialize
def serialize(root):
    def helper(node):
        if not node:
            return 'null,'
        return str(node.val) + ',' + helper(node.left) + helper(node.right)
    return helper(root)

def deserialize(data):
    def helper(nodes):
        val = nodes.pop(0)
        if val == 'null':
            return None
        node = TreeNode(int(val))
        node.left = helper(nodes)
        node.right = helper(nodes)
        return node
    return helper(data.split(','))

Summary

Trees are fundamental data structures used in various applications like databases, file systems, and search engines. Mastering tree operations and problem-solving techniques is crucial for technical interviews.