Tree & Binary Tree Data Structures in Python – DSA

      Ankush More

      Table of Contents

      1. Introduction to Trees
      2. Tree Terminology
      3. Types of Trees
      4. Binary Tree Fundamentals
      5. Binary Tree Implementation
      6. Tree Traversal Methods
      7. Binary Search Tree (BST)
      8. Common Tree Problems
      9. Advanced Topics
      10. Best Practices

      Introduction to Trees

      A Tree is a non-linear hierarchical data structure consisting of nodes connected by edges. Unlike linear data structures (arrays, linked lists, stacks, queues), trees allow for hierarchical relationships.

      Real-World Analogies

      • Family tree (genealogy)
      • Organization hierarchy (CEO → Managers → Employees)
      • File system (folders and files)
      • HTML DOM (Document Object Model)
      • Decision trees
      • Tournament brackets

      Why Use Trees?

      • Hierarchical Data: Natural representation of hierarchical relationships
      • Fast Search: O(log n) search in balanced trees
      • Flexible Size: Dynamic memory allocation
      • Efficient Operations: Insert, delete, search in O(log n)

      Tree Terminology

      Basic Terms

               A          ← Root
        / \
       B   C        ← Level 1
      / \   \
     D   E   F      ← Level 2 (Leaves: D, E, F)
      Python
      TermDefinitionExample
      RootTopmost node with no parentA
      ParentNode with childrenB is parent of D and E
      ChildNode descended from another nodeD and E are children of B
      LeafNode with no childrenD, E, F
      Internal NodeNode with at least one childA, B, C
      EdgeConnection between nodesA→B, B→D
      PathSequence of nodes and edgesA→B→D
      HeightLongest path from root to leaf2 (A→B→D)
      DepthDistance from root to nodeDepth of E is 2
      LevelDepth + 1Root is level 0 or 1
      SubtreeTree formed by a node and descendantsB with D, E
      DegreeNumber of children of a nodeDegree of B is 2
      AncestorAll nodes on path from root to nodeA, B are ancestors of D
      DescendantAll nodes in subtreeD, E are descendants of B
      SiblingNodes with same parentB and C are siblings

      Tree Properties

      def tree_properties():
    """Important tree properties"""
    properties = {
        "Maximum nodes at level l": "2^l",
        "Maximum nodes in tree of height h": "2^(h+1) - 1",
        "Minimum height with n nodes": "log₂(n+1) - 1",
        "For n nodes, number of edges": "n - 1",
        "Height of empty tree": "-1",
        "Height of tree with one node": "0"
    }
    return properties
      Python

      Types of Trees

      1. Binary Tree

      Each node has at most 2 children (left and right).

      2. Binary Search Tree (BST)

      Binary tree with ordering property: left < parent < right.

      3. AVL Tree

      Self-balancing BST with height difference ≤ 1.

      4. Red-Black Tree

      Self-balancing BST with color properties.

      5. B-Tree

      Multi-way tree used in databases and file systems.

      6. Heap

      Complete binary tree with heap property (min-heap or max-heap).

      7. Trie (Prefix Tree)

      Tree for storing strings with common prefixes.

      8. Segment Tree

      Tree for range queries and updates.

      9. N-ary Tree

      Tree where each node can have up to N children.

      Binary Tree Fundamentals

      What is a Binary Tree?

      A Binary Tree is a tree where each node has at most two children, referred to as left child and right child.

      Types of Binary Trees

      1. Full Binary Tree

      Every node has 0 or 2 children.

             A
      / \
     B   C
    / \
   D   E
      Python

      2. Complete Binary Tree

      All levels are filled except possibly the last, which is filled from left to right.

             A
      / \
     B   C
    / \  /
   D  E F
      Python

      3. Perfect Binary Tree

      All internal nodes have 2 children and all leaves are at same level.

             A
      / \
     B   C
    / \ / \
   D  E F  G
      Python

      4. Balanced Binary Tree

      Height difference between left and right subtrees ≤ 1 for all nodes.

      5. Degenerate (Skewed) Tree

      Each parent has only one child (essentially a linked list).

      A
 \
  B
   \
    C
     \
      D
      Python

      Binary Tree Implementation

      Basic Node Structure

      class TreeNode:
    """Basic binary tree node"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return f"TreeNode({self.val})"


class BinaryTree:
    """Binary tree implementation"""

    def __init__(self, root=None):
        self.root = root

    def insert_level_order(self, arr):
        """Create tree from array (level-order)"""
        if not arr:
            return None

        self.root = TreeNode(arr[0])
        queue = [self.root]
        i = 1

        while queue and i < len(arr):
            node = queue.pop(0)

            # Left child
            if i < len(arr) and arr[i] is not None:
                node.left = TreeNode(arr[i])
                queue.append(node.left)
            i += 1

            # Right child
            if i < len(arr) and arr[i] is not None:
                node.right = TreeNode(arr[i])
                queue.append(node.right)
            i += 1

        return self.root

    def height(self, node=None):
        """Calculate height of tree"""
        if node is None:
            node = self.root

        if node is None:
            return -1

        left_height = self.height(node.left)
        right_height = self.height(node.right)

        return max(left_height, right_height) + 1

    def size(self, node=None):
        """Count number of nodes"""
        if node is None:
            node = self.root

        if node is None:
            return 0

        return 1 + self.size(node.left) + self.size(node.right)

    def is_empty(self):
        """Check if tree is empty"""
        return self.root is None


# Example usage
tree = BinaryTree()
tree.insert_level_order([1, 2, 3, 4, 5, 6, 7])

print(f"Height: {tree.height()}")  # 2
print(f"Size: {tree.size()}")      # 7
print(f"Empty: {tree.is_empty()}")  # False
      Python

      Alternative Node Implementation with Parent Pointer

      class TreeNodeWithParent:
    """Binary tree node with parent pointer"""

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

    def is_root(self):
        return self.parent is None

    def is_leaf(self):
        return self.left is None and self.right is None

    def is_left_child(self):
        return self.parent and self.parent.left == self

    def is_right_child(self):
        return self.parent and self.parent.right == self

    def has_left_child(self):
        return self.left is not None

    def has_right_child(self):
        return self.right is not None

    def has_both_children(self):
        return self.left and self.right

    def has_any_children(self):
        return self.left or self.right
      Python

      Tree Traversal Methods

      1. Depth-First Search (DFS) Traversals

      A. Inorder Traversal (Left → Root → Right)

      Used in BST to get sorted order.

      def inorder_recursive(root):
    """Inorder: Left → Root → Right"""
    result = []

    def traverse(node):
        if node:
            traverse(node.left)
            result.append(node.val)
            traverse(node.right)

    traverse(root)
    return result


def inorder_iterative(root):
    """Inorder traversal using stack"""
    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)

        # Go to right subtree
        current = current.right

    return result


# Example
#       1
#      / \
#     2   3
#    / \
#   4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(inorder_recursive(root))   # [4, 2, 5, 1, 3]
print(inorder_iterative(root))   # [4, 2, 5, 1, 3]
      Python

      B. Preorder Traversal (Root → Left → Right)

      Used for creating copy of tree.

      def preorder_recursive(root):
    """Preorder: Root → Left → Right"""
    result = []

    def traverse(node):
        if node:
            result.append(node.val)
            traverse(node.left)
            traverse(node.right)

    traverse(root)
    return result


def preorder_iterative(root):
    """Preorder traversal using stack"""
    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


print(preorder_recursive(root))   # [1, 2, 4, 5, 3]
print(preorder_iterative(root))   # [1, 2, 4, 5, 3]
      Python

      C. Postorder Traversal (Left → Right → Root)

      Used for deleting tree, calculating expression tree.

      def postorder_recursive(root):
    """Postorder: Left → Right → Root"""
    result = []

    def traverse(node):
        if node:
            traverse(node.left)
            traverse(node.right)
            result.append(node.val)

    traverse(root)
    return result


def postorder_iterative(root):
    """Postorder traversal using two stacks"""
    if not root:
        return []

    stack1 = [root]
    stack2 = []

    while stack1:
        node = stack1.pop()
        stack2.append(node)

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

    result = []
    while stack2:
        result.append(stack2.pop().val)

    return result


print(postorder_recursive(root))   # [4, 5, 2, 3, 1]
print(postorder_iterative(root))   # [4, 5, 2, 3, 1]
      Python

      2. Breadth-First Search (BFS) Traversal

      Level Order Traversal

      from collections import deque

def level_order(root):
    """Level order traversal (BFS)"""
    if not root:
        return []

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

    while queue:
        node = queue.popleft()
        result.append(node.val)

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

    return result


def level_order_by_level(root):
    """Level order with each level in separate list"""
    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


print(level_order(root))           # [1, 2, 3, 4, 5]
print(level_order_by_level(root))  # [[1], [2, 3], [4, 5]]
      Python

      3. Other Traversal Types

      Reverse Level Order

      def reverse_level_order(root):
    """Level order traversal from bottom to top"""
    if not root:
        return []

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

    while queue:
        node = queue.popleft()
        result.append(node.val)

        # Add right before left for reverse
        if node.right:
            queue.append(node.right)
        if node.left:
            queue.append(node.left)

    return result[::-1]


print(reverse_level_order(root))  # [4, 5, 3, 2, 1]
      Python

      Zigzag Level Order

      def zigzag_level_order(root):
    """Zigzag (spiral) level order traversal"""
    if not root:
        return []

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

    while queue:
        level_size = len(queue)
        current_level = deque()

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

            if left_to_right:
                current_level.append(node.val)
            else:
                current_level.appendleft(node.val)

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

        result.append(list(current_level))
        left_to_right = not left_to_right

    return result


print(zigzag_level_order(root))  # [[1], [3, 2], [4, 5]]
      Python

      Vertical Order Traversal

      from collections import defaultdict, deque

def vertical_order(root):
    """Vertical order traversal"""
    if not root:
        return []

    # Map column to nodes
    column_table = defaultdict(list)
    queue = deque([(root, 0)])  # (node, column)

    while queue:
        node, column = queue.popleft()
        column_table[column].append(node.val)

        if node.left:
            queue.append((node.left, column - 1))
        if node.right:
            queue.append((node.right, column + 1))

    # Sort by column and return values
    result = []
    for col in sorted(column_table.keys()):
        result.append(column_table[col])

    return result


print(vertical_order(root))  # [[4], [2], [1, 5], [3]]
      Python

      4. Morris Traversal (Space-Optimized)

      Inorder traversal without using stack or recursion (O(1) space).

      def morris_inorder(root):
    """Morris inorder traversal - O(1) space"""
    result = []
    current = root

    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            # Find inorder predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if not predecessor.right:
                # Create thread
                predecessor.right = current
                current = current.left
            else:
                # Remove thread
                predecessor.right = None
                result.append(current.val)
                current = current.right

    return result


print(morris_inorder(root))  # [4, 2, 5, 1, 3]
      Python

      Binary Search Tree (BST)

      BST Property

      For every node:

      • All values in left subtree < node value
      • All values in right subtree > node value

      BST Implementation

      class BST:
    """Binary Search Tree implementation"""

    def __init__(self):
        self.root = None

    def insert(self, val):
        """Insert value into BST"""
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert_recursive(self.root, val)

    def _insert_recursive(self, node, val):
        """Helper for recursive insertion"""
        if val < node.val:
            if node.left:
                self._insert_recursive(node.left, val)
            else:
                node.left = TreeNode(val)
        else:
            if node.right:
                self._insert_recursive(node.right, val)
            else:
                node.right = TreeNode(val)

    def insert_iterative(self, val):
        """Insert value iteratively"""
        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)
                    break
                current = current.left
            else:
                if not current.right:
                    current.right = TreeNode(val)
                    break
                current = current.right

    def search(self, val):
        """Search for value in BST"""
        return self._search_recursive(self.root, val)

    def _search_recursive(self, node, val):
        """Helper for recursive search"""
        if not node or node.val == val:
            return node

        if val < node.val:
            return self._search_recursive(node.left, val)
        else:
            return self._search_recursive(node.right, val)

    def search_iterative(self, val):
        """Search iteratively"""
        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 find_min(self, node=None):
        """Find minimum value"""
        if node is None:
            node = self.root

        if not node:
            return None

        while node.left:
            node = node.left

        return node.val

    def find_max(self, node=None):
        """Find maximum value"""
        if node is None:
            node = self.root

        if not node:
            return None

        while node.right:
            node = node.right

        return node.val

    def delete(self, val):
        """Delete value from BST"""
        self.root = self._delete_recursive(self.root, val)

    def _delete_recursive(self, node, val):
        """Helper for recursive deletion"""
        if not node:
            return None

        if val < node.val:
            node.left = self._delete_recursive(node.left, val)
        elif val > node.val:
            node.right = self._delete_recursive(node.right, val)
        else:
            # Node to delete found

            # Case 1: No children (leaf)
            if not node.left and not node.right:
                return None

            # Case 2: One child
            if not node.left:
                return node.right
            if not node.right:
                return node.left

            # Case 3: Two children
            # Find inorder successor (min in right subtree)
            min_val = self.find_min(node.right)
            node.val = min_val
            node.right = self._delete_recursive(node.right, min_val)

        return node

    def inorder(self):
        """Return inorder traversal (sorted)"""
        result = []

        def traverse(node):
            if node:
                traverse(node.left)
                result.append(node.val)
                traverse(node.right)

        traverse(self.root)
        return result


# Example usage
bst = BST()
values = [50, 30, 70, 20, 40, 60, 80]
for val in values:
    bst.insert(val)

print(f"Inorder (sorted): {bst.inorder()}")  # [20, 30, 40, 50, 60, 70, 80]
print(f"Search 40: {bst.search(40)}")        # TreeNode(40)
print(f"Search 25: {bst.search(25)}")        # None
print(f"Min: {bst.find_min()}")              # 20
print(f"Max: {bst.find_max()}")              # 80

bst.delete(50)
print(f"After deleting 50: {bst.inorder()}")  # [20, 30, 40, 60, 70, 80]
      Python

      BST Validation

      def is_valid_bst(root):
    """Check if tree is a valid BST"""

    def validate(node, min_val, max_val):
        if not node:
            return True

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

        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    return validate(root, float('-inf'), float('inf'))


# Test
bst_root = TreeNode(5)
bst_root.left = TreeNode(3)
bst_root.right = TreeNode(7)
bst_root.left.left = TreeNode(1)
bst_root.left.right = TreeNode(4)

print(is_valid_bst(bst_root))  # True

# Invalid BST
invalid = TreeNode(5)
invalid.left = TreeNode(3)
invalid.right = TreeNode(7)
invalid.left.right = TreeNode(6)  # Violates BST property

print(is_valid_bst(invalid))  # False
      Python

      Common Tree Problems

      1. Maximum Depth (Height)

      def max_depth(root):
    """
    Find maximum depth of binary tree
    LeetCode #104
    """
    if not root:
        return 0

    return 1 + max(max_depth(root.left), max_depth(root.right))


# Iterative using level-order
def max_depth_iterative(root):
    if not root:
        return 0

    queue = deque([root])
    depth = 0

    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
      Python

      2. Minimum Depth

      def min_depth(root):
    """
    Find minimum depth (root to nearest leaf)
    LeetCode #111
    """
    if not root:
        return 0

    if not root.left and not root.right:
        return 1

    if not root.left:
        return 1 + min_depth(root.right)

    if not root.right:
        return 1 + min_depth(root.left)

    return 1 + min(min_depth(root.left), min_depth(root.right))
      Python

      3. Symmetric Tree

      def is_symmetric(root):
    """
    Check if tree is symmetric (mirror of itself)
    LeetCode #101
    """
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False

        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root, root) if root else True
      Python

      4. Invert Binary Tree

      def invert_tree(root):
    """
    Invert (mirror) binary tree
    LeetCode #226
    """
    if not root:
        return None

    # Swap children
    root.left, root.right = root.right, root.left

    # Recursively invert subtrees
    invert_tree(root.left)
    invert_tree(root.right)

    return root


# Iterative version
def invert_tree_iterative(root):
    if not root:
        return None

    queue = deque([root])

    while queue:
        node = queue.popleft()

        # Swap children
        node.left, node.right = node.right, node.left

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

    return root
      Python

      5. Same Tree

      def is_same_tree(p, q):
    """
    Check if two trees are identical
    LeetCode #100
    """
    if not p and not q:
        return True

    if not p or not q:
        return False

    return (p.val == q.val and
            is_same_tree(p.left, q.left) and
            is_same_tree(p.right, q.right))
      Python

      6. Balanced Binary Tree

      def is_balanced(root):
    """
    Check if tree is height-balanced
    LeetCode #110
    """
    def check_height(node):
        if not node:
            return 0

        left_height = check_height(node.left)
        if left_height == -1:
            return -1

        right_height = check_height(node.right)
        if right_height == -1:
            return -1

        if abs(left_height - right_height) > 1:
            return -1

        return max(left_height, right_height) + 1

    return check_height(root) != -1

      7. Diameter of Binary Tree

      def diameter_of_binary_tree(root):
    """
    Find diameter (longest path between any two nodes)
    LeetCode #543
    """
    diameter = [0]

    def height(node):
        if not node:
            return 0

        left = height(node.left)
        right = height(node.right)

        # Update diameter
        diameter[0] = max(diameter[0], left + right)

        return 1 + max(left, right)

    height(root)
    return diameter[0]
      Python

      8. Path Sum

      def has_path_sum(root, target_sum):
    """
    Check if there's a root-to-leaf path with given sum
    LeetCode #112
    """
    if not root:
        return False

    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))


def path_sum_all(root, target_sum):
    """
    Find all root-to-leaf paths with given sum
    LeetCode #113
    """
    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[:])

        dfs(node.left, remaining - node.val, path)
        dfs(node.right, remaining - node.val, path)

        path.pop()

    dfs(root, target_sum, [])
    return result
      Python

      9. Lowest Common Ancestor (LCA)

      def lowest_common_ancestor(root, p, q):
    """
    Find lowest common ancestor of two nodes
    LeetCode #236
    """
    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)

    if left and right:
        return root

    return left if left else right


def lowest_common_ancestor_bst(root, p, q):
    """
    LCA in Binary Search Tree
    LeetCode #235
    """
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root
      Python

      10. Serialize and Deserialize Binary Tree

      class Codec:
    """
    Serialize and deserialize binary tree
    LeetCode #297
    """

    def serialize(self, root):
        """Encode tree to string"""
        def dfs(node):
            if not node:
                vals.append('#')
            else:
                vals.append(str(node.val))
                dfs(node.left)
                dfs(node.right)

        vals = []
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        """Decode string to tree"""
        def dfs():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node

        vals = iter(data.split(','))
        return dfs()


# Test
codec = Codec()
tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.right.left = TreeNode(4)
tree.right.right = TreeNode(5)

serialized = codec.serialize(tree)
print(f"Serialized: {serialized}")  # 1,2,#,#,3,4,#,#,5,#,#

deserialized = codec.deserialize(serialized)
print(f"Deserialized: {codec.serialize(deserialized)}")
      Python

      11. Binary Tree Right Side View

      def right_side_view(root):
    """
    Return values visible from right side
    LeetCode #199
    """
    if not root:
        return []

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

    while queue:
        level_size = len(queue)

        for i in range(level_size):
            node = queue.popleft()

            # Last node in level
            if i == level_size - 1:
                result.append(node.val)

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

    return result
      Python

      12. Construct Binary Tree from Traversals

      def build_tree_from_preorder_inorder(preorder, inorder):
    """
    Build tree from preorder and inorder traversals
    LeetCode #105
    """
    if not preorder or not inorder:
        return None

    root = TreeNode(preorder[0])
    mid = inorder.index(preorder[0])

    root.left = build_tree_from_preorder_inorder(
        preorder[1:mid+1], inorder[:mid]
    )
    root.right = build_tree_from_preorder_inorder(
        preorder[mid+1:], inorder[mid+1:]
    )

    return root


def build_tree_from_inorder_postorder(inorder, postorder):
    """
    Build tree from inorder and postorder traversals
    LeetCode #106
    """
    if not inorder or not postorder:
        return None

    root = TreeNode(postorder[-1])
    mid = inorder.index(postorder[-1])

    root.left = build_tree_from_inorder_postorder(
        inorder[:mid], postorder[:mid]
    )
    root.right = build_tree_from_inorder_postorder(
        inorder[mid+1:], postorder[mid:-1]
    )

    return root
      Python

      13. Flatten Binary Tree to Linked List

      def flatten(root):
    """
    Flatten tree to linked list (preorder)
    LeetCode #114
    """
    if not root:
        return

    # Flatten left and right subtrees
    flatten(root.left)
    flatten(root.right)

    # Save right subtree
    right = root.right

    # Move left to right
    root.right = root.left
    root.left = None

    # Attach saved right to end
    current = root
    while current.right:
        current = current.right
    current.right = right
      Python

      14. Count Complete Tree Nodes

      def count_nodes(root):
    """
    Count nodes in complete binary tree
    LeetCode #222 - O(log²n) solution
    """
    if not root:
        return 0

    def get_height(node):
        height = 0
        while node:
            height += 1
            node = node.left
        return height

    left_height = get_height(root.left)
    right_height = get_height(root.right)

    if left_height == right_height:
        # Left subtree is perfect
        return (1 << left_height) + count_nodes(root.right)
    else:
        # Right subtree is perfect
        return (1 << right_height) + count_nodes(root.left)
      Python

      Advanced Topics

      1. Binary Tree Maximum Path Sum

      def max_path_sum(root):
    """
    Find maximum path sum (any node to any node)
    LeetCode #124
    """
    max_sum = [float('-inf')]

    def max_gain(node):
        if not node:
            return 0

        # Max sum from left and right (ignore negative)
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # Path through current node
        price_newpath = node.val + left_gain + right_gain

        # Update global maximum
        max_sum[0] = max(max_sum[0], price_newpath)

        # Return max gain if continue from current node
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum[0]
      Python

      2. Binary Tree Cameras

      def min_camera_cover(root):
    """
    Minimum cameras needed to monitor all nodes
    LeetCode #968
    """
    cameras = [0]

    def dfs(node):
        # Returns: 0=needs coverage, 1=has camera, 2=covered
        if not node:
            return 2

        left = dfs(node.left)
        right = dfs(node.right)

        # If any child needs coverage, place camera here
        if left == 0 or right == 0:
            cameras[0] += 1
            return 1

        # If any child has camera, this is covered
        if left == 1 or right == 1:
            return 2

        # Both children are covered, this needs coverage
        return 0

    # If root needs coverage, add camera
    if dfs(root) == 0:
        cameras[0] += 1

    return cameras[0]
      Python

      3. Vertical Order Traversal (Sorted)

      def vertical_traversal(root):
    """
    Vertical order with sorting
    LeetCode #987
    """
    if not root:
        return []

    # (column, row, value)
    nodes = []

    def dfs(node, row, col):
        if node:
            nodes.append((col, row, node.val))
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

    dfs(root, 0, 0)

    # Sort by column, then row, then value
    nodes.sort()

    # Group by column
    result = []
    prev_col = float('-inf')

    for col, row, val in nodes:
        if col != prev_col:
            result.append([])
            prev_col = col
        result[-1].append(val)

    return result
      Python

      4. Morris Preorder Traversal

      def morris_preorder(root):
    """Morris preorder - O(1) space"""
    result = []
    current = root

    while current:
        if not current.left:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if not predecessor.right:
                result.append(current.val)
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                current = current.right

    return result
      Python

      5. Boundary of Binary Tree

      def boundary_of_binary_tree(root):
    """
    Return boundary nodes (anti-clockwise)
    LeetCode #545
    """
    if not root:
        return []

    def is_leaf(node):
        return not node.left and not node.right

    def add_left_boundary(node):
        while node:
            if not is_leaf(node):
                boundary.append(node.val)
            node = node.left if node.left else node.right

    def add_leaves(node):
        if node:
            if is_leaf(node):
                boundary.append(node.val)
            else:
                add_leaves(node.left)
                add_leaves(node.right)

    def add_right_boundary(node):
        stack = []
        while node:
            if not is_leaf(node):
                stack.append(node.val)
            node = node.right if node.right else node.left
        boundary.extend(reversed(stack))

    boundary = [root.val]

    if not is_leaf(root):
        add_left_boundary(root.left)
        add_leaves(root)
        add_right_boundary(root.right)

    return boundary
      Python

      6. All Nodes Distance K

      def distance_k(root, target, k):
    """
    Find all nodes at distance K from target
    LeetCode #863
    """
    # Build parent pointers
    parent = {}

    def build_parent(node, par=None):
        if node:
            parent[node] = par
            build_parent(node.left, node)
            build_parent(node.right, node)

    build_parent(root)

    # BFS from target
    queue = deque([(target, 0)])
    visited = {target}
    result = []

    while queue:
        node, dist = queue.popleft()

        if dist == k:
            result.append(node.val)
            continue

        # Explore children and parent
        for neighbor in (node.left, node.right, parent[node]):
            if neighbor and neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return result
      Python

      7. Recover Binary Search Tree

      def recover_tree(root):
    """
    Recover BST where two nodes are swapped
    LeetCode #99
    """
    first = second = prev = None

    def inorder(node):
        nonlocal first, second, prev

        if not node:
            return

        inorder(node.left)

        # Check if previous is greater than current
        if prev and prev.val > node.val:
            if not first:
                first = prev
            second = node

        prev = node
        inorder(node.right)

    inorder(root)

    # Swap values
    first.val, second.val = second.val, first.val
      Python

      8. Kth Smallest Element in BST

      def kth_smallest(root, k):
    """
    Find kth smallest element in BST
    LeetCode #230
    """
    stack = []
    current = root
    count = 0

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        count += 1

        if count == k:
            return current.val

        current = current.right
      Python

      Best Practices

      1. When to Use Trees

      Use trees when:

      • Hierarchical relationships exist
      • Fast search, insert, delete needed (BST)
      • Range queries required (segment tree)
      • Prefix matching needed (trie)
      • Priority queue operations (heap)

      2. Tree vs Other Data Structures

      """
Array:      O(1) access, O(n) search
Linked List: O(n) access, O(n) search
Hash Table:  O(1) average search, no order
BST:         O(log n) balanced search, maintains order
"""
      Python

      3. Common Patterns

      Pattern 1: Recursive Template

      def tree_function(root):
    # Base case
    if not root:
        return base_value

    # Recursive case
    left_result = tree_function(root.left)
    right_result = tree_function(root.right)

    # Combine results
    return combine(root.val, left_result, right_result)
      Python

      Pattern 2: Level Order Template

      def level_order_template(root):
    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
      Python

      Pattern 3: DFS with Path

      def dfs_with_path(root):
    result = []

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

        path.append(node.val)

        # Leaf node - found complete path
        if not node.left and not node.right:
            result.append(path[:])

        dfs(node.left, path)
        dfs(node.right, path)

        path.pop()  # Backtrack

    dfs(root, [])
    return result
      Python

      4. Performance Optimization

      # ✓ Use iterative for space efficiency
def iterative_traversal(root):
    stack = [root]
    # O(h) space instead of O(h) call stack

# ✓ Use Morris for O(1) space
def morris_traversal(root):
    # No extra space beyond result

# ✓ Cache results when needed
from functools import lru_cache

@lru_cache(maxsize=None)
def expensive_tree_operation(node):
    # Memoized results
    pass
      Python

      5. Testing Trees

      def create_test_tree():
    """Helper to create test trees"""
    #       1
    #      / \
    #     2   3
    #    / \
    #   4   5

    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    return root


def print_tree(root, level=0, prefix="Root: "):
    """Visual tree representation"""
    if root:
        print(" " * (level * 4) + prefix + str(root.val))
        if root.left or root.right:
            if root.left:
                print_tree(root.left, level + 1, "L--- ")
            else:
                print(" " * ((level + 1) * 4) + "L--- None")

            if root.right:
                print_tree(root.right, level + 1, "R--- ")
            else:
                print(" " * ((level + 1) * 4) + "R--- None")


# Test
tree = create_test_tree()
print_tree(tree)
      Python

      6. Type Hints

      from typing import Optional, List

class TreeNode:
    def __init__(self, val: int = 0, 
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None):
        self.val = val
        self.left = left
        self.right = right


def tree_function(root: Optional[TreeNode]) -> List[int]:
    """
    Process tree and return result

    Args:
        root: Root node of tree

    Returns:
        List of processed values
    """
    pass
      Python

      Summary

      Key Takeaways

      1. Hierarchical Structure: Trees represent hierarchical relationships
      2. Recursive Nature: Most tree problems solved recursively
      3. Traversal Methods: Inorder, preorder, postorder, level-order
      4. BST Property: Left < Root < Right enables O(log n) operations
      5. Common Patterns: DFS, BFS, divide-and-conquer
      6. Space-Time Tradeoff: Recursive vs iterative vs Morris

      Time Complexity Summary

      OperationArrayBST (Balanced)BST (Skewed)
      SearchO(n)O(log n)O(n)
      InsertO(n)O(log n)O(n)
      DeleteO(n)O(log n)O(n)
      Min/MaxO(n)O(log n)O(n)
      TraverseO(n)O(n)O(n)

      Quick Reference

      # Create node
node = TreeNode(val)

# Traversals
inorder(root)    # Left → Root → Right
preorder(root)   # Root → Left → Right
postorder(root)  # Left → Right → Root
level_order(root) # BFS

# Common operations
height(root)
is_balanced(root)
is_valid_bst(root)
lowest_common_ancestor(root, p, q)
      Python

      Interview Preparation Checklist

      Easy:

      • ✓ Tree traversals (all types)
      • ✓ Maximum depth
      • ✓ Same tree
      • ✓ Invert tree
      • ✓ Symmetric tree

      Medium:

      • ✓ BST operations
      • ✓ Level order traversal
      • ✓ Path sum
      • ✓ LCA
      • ✓ Serialize/deserialize

      Hard:

      • ✓ Maximum path sum
      • ✓ Binary tree cameras
      • ✓ Recover BST
      • ✓ Vertical order traversal

      Further Reading

      • AVL Trees (self-balancing)
      • Red-Black Trees
      • B-Trees and B+ Trees
      • Segment Trees
      • Trie Data Structure
      • Fenwick Tree (Binary Indexed Tree)

      Practice Resources:

      • LeetCode Tree Problems (150+)
      • Binary Tree Visualizer Tools
      • GeeksforGeeks Tree Articles
      • Cracking the Coding Interview

      Happy Coding! 🌳

      Discover more from Altgr Blog

      Subscribe to get the latest posts sent to your email.

      Related Posts

      Leave a Reply

      Your email address will not be published. Required fields are marked *