Skip to content
Software Engineering Hub

Trees

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear structures, trees represent parent-child relationships and are fundamental to many algorithms.

Interactive BST Builder

Build a Binary Search Tree by inserting values. Run in-order, pre-order, post-order, and level-order traversals to see the visit order highlighted on the tree.

Data Structure Visualizer

Ordered hierarchical structure

Insert
Value
Traversals
Insert values to build a BST
Try: 50, 30, 70, 20, 40, 60, 80

Tree Terminology

                    1         ← Root (level 0)
                  /   \
                 2     3      ← Level 1
                / \     \
               4   5     6    ← Level 2 (Leaves)
              /
             7                ← Level 3 (Leaf)


Terminology:
- Root: Node 1 (no parent)
- Parent of 4, 5: Node 2
- Children of 2: Nodes 4, 5
- Siblings: 4 and 5
- Leaf nodes: 5, 6, 7 (no children)
- Height of tree: 3 (longest path from root)
- Depth of node 4: 2 (distance from root)

Binary Tree Basics

A binary tree has at most two children per node (left and right).

Node Definition

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


# Create a tree
#       1
#      / \
#     2   3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

Tree Traversals

Depth-First Traversals

        1
       / \
      2   3
     / \
    4   5


Preorder  (Root, Left, Right): 1, 2, 4, 5, 3
Inorder   (Left, Root, Right): 4, 2, 5, 1, 3
Postorder (Left, Right, Root): 4, 5, 2, 3, 1
# Recursive traversals
def preorder(root):
    """Root → Left → Right"""
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)


def inorder(root):
    """Left → Root → Right"""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)


def postorder(root):
    """Left → Right → Root"""
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]


# Iterative preorder using stack
def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]


    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed first
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)


    return result


# Iterative inorder using stack
def inorder_iterative(root):
    result = []
    stack = []
    current = root


    while current or stack:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left
        # Process node
        current = stack.pop()
        result.append(current.val)
        # Move to right subtree
        current = current.right


    return result

Breadth-First (Level Order) Traversal

Level Order Traversal Visualization:


        1         Level 0: [1]
       / \
      2   3       Level 1: [2, 3]
     / \   \
    4   5   6     Level 2: [4, 5, 6]


Queue processing:
Step 1: queue = [1] → process 1, add 2, 3
Step 2: queue = [2, 3] → process 2, add 4, 5; process 3, add 6
Step 3: queue = [4, 5, 6] → process all (leaves)


Output: [[1], [2, 3], [4, 5, 6]]
from collections import deque


def level_order(root):
    """
    Return nodes grouped by level.
    Time: O(n), Space: O(n)


    Algorithm:
    1. Use queue for BFS
    2. Process all nodes at current level
    3. Add their children to queue for next level
    """
    if not root:
        return []


    result = []
    queue = deque([root])


    while queue:
        level_size = len(queue)
        current_level = []


        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)


            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)


        result.append(current_level)


    return result


# Example output: [[1], [2, 3], [4, 5, 6]]

Binary Search Tree (BST)

A BST maintains the property: left < root < right for all nodes.

        8         ← All values in left subtree < 8
       / \           All values in right subtree > 8
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

BST Operations

class BST:
    def __init__(self):
        self.root = None


    def insert(self, val):
        """Insert value into BST. Time: O(h)"""
        if not self.root:
            self.root = TreeNode(val)
            return


        current = self.root
        while True:
            if val < current.val:
                if not current.left:
                    current.left = TreeNode(val)
                    return
                current = current.left
            else:
                if not current.right:
                    current.right = TreeNode(val)
                    return
                current = current.right


    def search(self, val):
        """Search for value. Time: O(h)"""
        current = self.root
        while current:
            if val == current.val:
                return current
            elif val < current.val:
                current = current.left
            else:
                current = current.right
        return None


    def delete(self, val):
        """Delete value from BST. Time: O(h)"""
        def delete_node(node, val):
            if not node:
                return None


            if val < node.val:
                node.left = delete_node(node.left, val)
            elif val > node.val:
                node.right = delete_node(node.right, val)
            else:
                # Node found
                if not node.left:
                    return node.right
                if not node.right:
                    return node.left
                # Two children: find inorder successor
                successor = node.right
                while successor.left:
                    successor = successor.left
                node.val = successor.val
                node.right = delete_node(node.right, successor.val)


            return node


        self.root = delete_node(self.root, val)

Time Complexity

OperationAverageWorst (Skewed)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)
TraversalO(n)O(n)

Worst case occurs when tree becomes a linked list (unbalanced)

Common Patterns

1. Maximum Depth

def max_depth(root):
    """
    Find height of tree.
    Time: O(n), Space: O(h)


    Algorithm:
    1. Base case: empty tree has depth 0
    2. Recursively find depth of left and right subtrees
    3. Return 1 + max of both depths
    """
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


# Iterative BFS approach
from collections import deque


def max_depth_bfs(root):
    if not root:
        return 0


    depth = 0
    queue = deque([root])


    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)


    return depth

2. Validate BST

Validate BST using bounds:


Valid BST - each node must be within (min, max) bounds


        5 (−∞, +∞)
       / \
      3   7 must be in (5, +∞)
     / \
    2   4 must be in (3, 5)


For node 3: valid if 3 > −∞ AND 3 < 5 ✓
For node 4: valid if 4 > 3 AND 4 < 5 ✓
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
    """
    Check if tree is valid BST.
    Time: O(n), Space: O(h)


    Algorithm:
    1. Each node must be within valid range (min, max)
    2. Left child: upper bound becomes parent value
    3. Right child: lower bound becomes parent value
    """
    if not root:
        return True


    if root.val <= min_val or root.val >= max_val:
        return False


    return (is_valid_bst(root.left, min_val, root.val) and
            is_valid_bst(root.right, root.val, max_val))


# Alternative: Inorder traversal should be sorted
def is_valid_bst_inorder(root):
    prev = float('-inf')


    def inorder(node):
        nonlocal prev
        if not node:
            return True


        if not inorder(node.left):
            return False


        if node.val <= prev:
            return False
        prev = node.val


        return inorder(node.right)


    return inorder(root)

3. Lowest Common Ancestor (BST)

LCA in BST:


        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5


LCA(2, 8) = 6  (split point)
LCA(2, 4) = 2  (one is ancestor)
LCA(3, 5) = 4  (both in same subtree)


Algorithm: Find where p and q split (go different directions)
def lowest_common_ancestor(root, p, q):
    """
    Find LCA in BST.
    Time: O(h), Space: O(1)


    Algorithm:
    - If both p and q < current: LCA is in left subtree
    - If both p and q > current: LCA is in right subtree
    - Otherwise: current is LCA (split point)
    """
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current
    return None


# For general binary tree (not BST)
def lca_binary_tree(root, p, q):
    if not root or root == p or root == q:
        return root


    left = lca_binary_tree(root.left, p, q)
    right = lca_binary_tree(root.right, p, q)


    if left and right:
        return root
    return left if left else right

4. Path Sum

def has_path_sum(root, target_sum):
    """
    Check if root-to-leaf path equals target.
    Time: O(n), Space: O(h)


    Algorithm:
    1. Base case: null node returns False
    2. At leaf: check if remaining sum equals node value
    3. Recurse: subtract current value and check children
    """
    if not root:
        return False


    # Check if leaf node
    if not root.left and not root.right:
        return root.val == target_sum


    remaining = target_sum - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))


# Find all paths that sum to target
def path_sum_all(root, target_sum):
    result = []


    def dfs(node, remaining, path):
        if not node:
            return


        path.append(node.val)


        if not node.left and not node.right and remaining == node.val:
            result.append(path[:])
        else:
            dfs(node.left, remaining - node.val, path)
            dfs(node.right, remaining - node.val, path)


        path.pop()  # Backtrack


    dfs(root, target_sum, [])
    return result

5. Invert Binary Tree

Invert (Mirror) Binary Tree:


Original:           Inverted:
      4                  4
     / \                / \
    2   7      →       7   2
   / \ / \            / \ / \
  1  3 6  9          9  6 3  1


Algorithm: Swap left and right children at each node
def invert_tree(root):
    """
    Mirror the tree.
    Time: O(n), Space: O(h)


    Algorithm:
    1. Base case: null returns null
    2. Swap left and right children
    3. Recursively invert both subtrees
    """
    if not root:
        return None


    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)


    return root


# Iterative using BFS
from collections import deque


def invert_tree_bfs(root):
    if not root:
        return None


    queue = deque([root])


    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left


        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)


    return root

6. Serialize and Deserialize

class Codec:
    """
    Encode tree to string and decode back.
    Time: O(n) for both operations
    Space: O(n)
    """
    def serialize(self, root):
        """Encode tree to string using preorder"""
        if not root:
            return "null,"
        return (str(root.val) + "," +
                self.serialize(root.left) +
                self.serialize(root.right))


    def deserialize(self, data):
        """Decode string to tree"""
        def build():
            val = next(values)
            if val == "null":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node


        values = iter(data.split(","))
        return build()


# Example:
#       1
#      / \
#     2   3
#        / \
#       4   5
# Serialized: "1,2,null,null,3,4,null,null,5,null,null,"

Tree Types

TypeDescription
Binary TreeAt most 2 children per node
BSTLeft < Root < Right
Balanced BSTHeight = O(log n): AVL, Red-Black
Complete BinaryAll levels filled except possibly last
Perfect BinaryAll leaves at same level, all nodes have 2 children
Full BinaryEvery node has 0 or 2 children

Practice Problems

Easy

ProblemPatternCompanies
Maximum DepthDFSAmazon, Google
Invert Binary TreeRecursionGoogle, Amazon
Same TreeRecursionAmazon, Microsoft
Symmetric TreeRecursionAmazon, Microsoft

Medium

ProblemPatternCompanies
Validate BSTInorder/BoundsAmazon, Meta
Level Order TraversalBFSAmazon, Google
Construct BST from PreorderRecursionAmazon, Google
Lowest Common AncestorRecursionMeta, Amazon
Binary Tree Right Side ViewBFSMeta, Amazon

Hard

ProblemPatternCompanies
Serialize and DeserializePreorderMeta, Google
Binary Tree Maximum Path SumDFSMeta, Google
Recover Binary Search TreeInorderAmazon, Microsoft

Key Takeaways

  1. Traversal order matters - Inorder on BST gives sorted order
  2. Recursion is natural - Trees are recursive structures
  3. BST property - Enables O(log n) search on balanced trees
  4. Balance matters - Unbalanced trees degrade to O(n)
  5. BFS vs DFS - BFS for levels, DFS for paths

Next Steps

Heaps Learn about priority queues and heap operations
Graphs Extend tree concepts to general graph structures