Skip to content
Data Structures & Algorithms

Binary Tree interview questions and answers

53 questions, 29 with code. About 4 h 44 min to read them all.

By TestLab · Updated

Plan for an interview
53 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is a tree data structure and how does it work?

A tree data structure is a hierarchical collection of connected nodes in which each node has one parent, except the root, and zero or more children. Trees model relationships such as file systems, organization charts, database indexes, and decision processes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concepts

A tree is normally rooted, meaning it has one top node called the root.

  • Node: Contains a value and references to its children.

  • Edge: A connection between a parent and a child.

  • Root: The node without a parent.

  • Leaf: A node without children.

  • Parent and child: Nodes directly connected in the hierarchy.

  • Depth: The number of edges from the root to a node; the root has depth 0.

  • Height: The number of edges along the longest downward path to a leaf; a single-node tree has height 0.

  • Subtree: Any node together with all of its descendants.

A general tree allows each node to have any number of children. A binary tree restricts every node to at most two children, conventionally named left and right.

Common Tree Variants

These terms describe different properties and should not be used interchangeably:

  • Binary tree: Each node has at most two children.

  • Binary search tree (BST): A binary tree with an ordering rule: values in a node’s left subtree are smaller, and values in its right subtree are larger. A duplicate-key policy must be defined separately.

  • Complete binary tree: Every level except possibly the last is full, and the last level is filled from left to right.

  • Full binary tree: Every node has either exactly zero or exactly two children.

  • Perfect binary tree: Every internal node has two children, and every leaf is at the same depth. It is both full and complete.

  • Balanced tree: A tree whose height remains O(log n). One common height-balancing invariant, used by AVL trees, requires the left and right subtree heights at every node to differ by at most one.

How Trees Are Represented

A binary tree is commonly represented through references:

  • left points to the left child.

  • right points to the right child.

  • In the Python 3.12 representation, both are None when the child does not exist.

Other representations include parent pointers, adjacency lists, and array-based layouts such as heap indexing. The representation does not change the tree’s logical hierarchy.

Preorder, inorder, and postorder traversals can be implemented recursively or iteratively with an explicit stack. Level-order traversal uses breadth-first search with a queue, normally collections.deque in Python.

Unlike a list or queue, a tree does not define one universal traversal. The required order depends on the application: parent-before-child, children-before-parent, sorted order, or level-by-level processing.

Complexity

Let n be the number of nodes, h the tree height, and w the maximum number of nodes on one level.

Operation Best Average Worst Auxiliary space
Access the root O(1) O(1) O(1) O(1)
Traverse all nodes O(n) O(n) O(n) O(h) for recursive DFS; O(w) for BFS
Search by value in an unordered binary tree O(1) O(n) O(n) O(1) iterative or O(h) recursive
Search in a BST O(1) O(log n) O(n) O(1) iterative or O(h) recursive
Insert into a BST O(1) O(log n) O(n) O(1) iterative or O(h) recursive

Traversal is linear because every node is visited once. A BST operation follows one root-to-leaf path, taking O(h); it becomes O(n) when the tree is skewed. Average BST bounds assume a reasonably balanced tree or random insertion order.

Auxiliary space includes the recursion stack or queue but excludes the input tree itself. The stored tree occupies O(n) space. DFS uses O(h) stack space, while BFS uses O(w) queue space.

Example and Traversal Orders

Consider the tree A(B(D, E), C), where A is the root, B and C are its children, and D and E are leaves.

  • Preorder, root-left-right: A, B, D, E, C

  • Inorder, left-root-right: D, B, E, A, C

  • Postorder, left-right-root: D, E, B, C, A

  • Level order, breadth-first: A, B, C, D, E

For a BST with distinct keys, inorder traversal produces values in sorted order. For an arbitrary binary tree, it simply visits the left subtree, the node, and then the right subtree.

Common Pitfalls and Interview Tips

  • Height convention: Height counts edges here, so an empty tree has height -1 and a one-node tree has height 0.

  • Edge cases: Define behavior for an empty tree and one-node tree. Negative values are valid; duplicates require a BST policy, and inserting already sorted values can create a skewed tree.

  • Recursion limits: Recursive traversal of a highly skewed tree can approach Python’s recursion limit of about 1000. Use an explicit stack when depth is not bounded.

  • Input mutation: Traversals should not change node links unless rebuilding the tree is intentional.

  • Trees versus graphs: A disconnected graph or a graph containing a cycle is not a valid tree. Use a visited set when processing general graph input.

  • Integer overflow: Python integers do not overflow, but node counts or indices may overflow in fixed-width languages.

  • BST assumptions: A BST search is not logarithmic unless the tree remains reasonably balanced.

  • Common follow-up: Interviewers often ask for iterative traversal, BST validation, lowest common ancestor, or maximum depth.

2

What is a binary tree in data structures?

A binary tree is a hierarchical data structure in which each node has at most two children, conventionally designated left and right. Unlike a binary search tree, a general binary tree does not require any ordering between the values in its subtrees.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concepts

  • Node: The basic unit containing a value and references to its children.

  • Root: The top node with no parent.

  • Leaf: A node with no children.

  • Parent: A node directly above another node.

  • Edge: A connection between a parent and a child.

  • Subtree: A node and all of its descendants.

  • Height: The number of edges on the longest downward path from the root to a leaf. Under this convention, an empty tree has height -1, and a tree containing one node has height 0.

  • Depth: The number of edges from the root to a node, so the root has depth 0.

The left and right positions are significant because the structure defines two distinct subtrees even if their contents are identical.

Small Example

Consider a tree whose root is 8, with left child 3 and right child 10. Node 3 has children 1 and 6, while node 10 has right child 14.

For this tree:

  • Preorder traversal, visiting root-left-right, produces 8, 3, 1, 6, 10, 14.

  • Inorder traversal, visiting left-root-right, produces 1, 3, 6, 8, 10, 14.

  • Postorder traversal, visiting left-right-root, produces 1, 6, 3, 14, 10, 8.

  • Level-order traversal, visiting each level from left to right, produces 8, 3, 10, 1, 6, 14.

An inorder traversal yields sorted values only when the tree also satisfies the binary search tree property.

Common Tree Types

Type Defining property
Binary tree Every node has at most two children.
Binary search tree (BST) Every key in the left subtree is smaller and every key in the right subtree is larger than the node’s key. A duplicate-key policy must also be defined.
Full tree Every node has either exactly zero children or exactly two children.
Complete tree Every level except possibly the last is completely filled, and nodes on the last level are filled from left to right.
Perfect tree Every internal node has exactly two children, and all leaves are at the same depth.
Balanced tree The heights of each node’s left and right subtrees differ by at most one, commonly resulting in height O(log n).

These properties are independent: a tree does not automatically satisfy one merely because it is binary.

Complexity

For a binary tree with n nodes and height h:

  • Searching or value-based lookup: Best case O(1) when the target is at the root; average case O(n) for an unstructured tree with a uniformly distributed target; worst case O(n) because the lack of an ordering guarantee may require inspecting every node. The average can be lower for favorable tree shapes and target distributions.

  • Balanced BST lookup: Best, average, and worst case O(log n) because the height is O(log n).

  • Full traversal: Best, average, and worst case O(n) time because every node is visited once.

  • DFS auxiliary space: O(h) for the recursion stack or explicit stack.

  • BFS auxiliary space: O(w), where w is the maximum number of nodes at one level.

  • Input storage: O(n) if the tree itself is counted; the auxiliary bounds above exclude the existing input tree.

For a balanced tree, h = O(log n). For a completely skewed tree, h = O(n), so recursive DFS may approach Python’s recursion limit.

Interview Tips

  • Do not confuse a binary tree with a BST; ordering is not part of the basic binary-tree definition.

  • State whether height counts nodes or edges. This answer uses edges.

  • Include the recursion stack when discussing space complexity.

  • Mention how duplicate values are handled when discussing BSTs.

  • Common follow-up questions ask for preorder, inorder, postorder, and level-order traversals; determining whether a tree is balanced; and finding its maximum depth.

3

What is a binary heap?

A binary heap is a complete binary tree that satisfies the heap-order property. In a min-heap, each parent is less than or equal to its children and the root is the minimum; in a max-heap, each parent is greater than or equal to its children and the root is the maximum. This structure supports efficient root access, insertion, and root removal.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Structure and Representation

A binary heap is commonly represented as a contiguous array. With zero-based indexing, a node at index i has:

  • Left child at 2 * i + 1

  • Right child at 2 * i + 2

  • Parent at (i - 1) // 2

For the min-heap array [1, 3, 2, 7, 6, 4, 5], the levels are:

Level Values from left to right
Root 1
Level 1 3, 2
Level 2 7, 6, 4
Level 3 5

The tree is complete: every level is full except possibly the last, which is filled from left to right.

Step-by-step insertion of 0 proceeds as follows:

  1. Append 0 at the next available index, producing [1, 3, 2, 7, 6, 4, 5, 0].

  2. Its parent is 7, so swap them: [1, 3, 2, 0, 6, 4, 5, 7].

  3. Its new parent is 3, so swap again: [1, 0, 2, 3, 6, 4, 5, 7].

  4. Its new parent is 1, so swap once more: [0, 1, 2, 3, 6, 4, 5, 7].

The heap property is restored, and insertion took O(log n) time in this worst-case walkthrough.

Heap Properties

A binary heap has two defining properties:

  • Heap-order property: Every parent satisfies the ordering appropriate to its heap type.

  • Min-heap: parent <= children.

  • Max-heap: parent >= children.

  • Shape property: The tree is complete.

These properties distinguish heaps from related structures:

Structure Defining property
Binary tree Each node has at most two children
Complete tree All levels are full except possibly the last, which is left-aligned
Full tree Every node has either zero or two children
Perfect tree All internal nodes have two children, and all leaves have equal depth
Height-balanced tree At every node, the left and right subtree heights differ by at most one
Binary search tree In the distinct-key form, all left-subtree keys are smaller and all right-subtree keys are larger
Binary heap Complete tree with min-heap or max-heap ordering

A binary heap is height-balanced, but it is not generally a binary search tree because it imposes no ordering between the left and right subtrees.

Core Operations

  • Peek: Read the root to obtain the minimum or maximum value.

  • Insert: Add the value at the next available array position, then sift it upward until heap order is restored.

  • Delete root: Replace the root with the last element, reduce the heap size, then sift that element downward.

  • Build heap: Convert an existing array into a heap using bottom-up heapification.

Python’s heapq implements a min-heap. A max-heap can be simulated for numeric values by negating them because heapq does not directly provide a max-heap.

Complexity

Let n be the number of elements and h the heap height. Using the convention that height counts edges, a nonempty complete heap has h = floor(log2(n)); an empty heap has height -1.

Operation Best Average Worst Reason
Peek root O(1) O(1) O(1) The root is stored at index 0
Insert O(1) O(log n) O(log n) Sifting may stop immediately or traverse all levels
Delete root O(log n) O(log n) O(log n) The replacement may sift toward a leaf
Build heap O(n) O(n) O(n) Bottom-up heapification processes subtrees of geometrically decreasing sizes
Search for an arbitrary value O(1) O(n) O(n) The heap is not ordered for general-purpose searching
Heap sort O(n log n) O(n log n) O(n log n) Building costs O(n), followed by n root removals

Total heap storage is O(n), including the input heap array. Iterative heap operations use O(1) auxiliary space. Recursive sifting uses O(h) = O(log n) auxiliary stack space.

Common Pitfalls

  • Reversing the parent-child inequalities for min-heaps and max-heaps.

  • Confusing heap order with binary search tree order: heaps order parents and children, not entire left and right subtrees.

  • Assuming arbitrary values can be found efficiently; binary heaps optimize root access, not general searching.

  • Removing an arbitrary element directly and thereby losing the complete-tree shape; standard root removal moves the last element first.

  • Using list.pop(0) or list.insert(0, value), which shifts elements and costs O(n).

  • Assuming heapq is a max-heap or attempting to negate nonnumeric values.

  • Forgetting the O(log n) recursion stack used by recursive sifting.

  • Edge cases: an empty heap has no root, a one-element heap is valid, duplicate and negative numeric values are allowed, and heapification accepts already sorted, reverse-sorted, or unsorted arrays.

4

What is a Binary Search Tree and its properties

A Binary Search Tree is a node-based binary tree data structure where each node has at most two children, arranged such that the left subtree contains values smaller than the node and the right subtree contains values larger. This ordering property allows for efficient searching, insertion, and deletion operations compared to unsorted linear structures.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Key Properties

The core invariant is that for any node N: - All values in the left subtree are less than N.val. - All values in the right subtree are greater than N.val. - Both left and right subtrees must also be Binary Search Trees.

It is important to distinguish a BST from other binary tree types:

Tree Type Constraint
Binary Tree Each node has at most 2 children, no ordering
Complete All levels full except last, filled left to right
Full Every node has 0 or 2 children
Perfect All leaves at the same depth
Balanced Height difference of subtrees is at most 1

How It Works

Operations rely on the ordering property to eliminate half of the remaining search space at each step. 1. Search: Compare the target with the current node. If equal, found. If smaller, go left; if larger, go right. 2. Insert: Traverse to find the correct leaf position following the search logic, then attach the new node. 3. Delete: Handle three cases: leaf node (remove directly), one child (replace with child), two children (replace with inorder successor or predecessor).

Complexity Analysis

Let n be the number of nodes and h be the height of the tree. - Search/Insert/Delete Time: - Best/Average: O(log n) when the tree is balanced. - Worst: O(n) when the tree is skewed (resembles a linked list). - Space Complexity: - Iterative: O(1) extra space (excluding input storage). - Recursive: O(h) for the call stack, which is O(log n) balanced or O(n) skewed.

Common Pitfalls

  • Assuming Balance: A BST built from sorted input becomes a linked list, degrading performance to O(n). Use self-balancing variants like AVL or Red-Black trees if guaranteed performance is needed.

  • Duplicate Handling: Decide how to handle duplicates (e.g., ignore or store in right subtree) before implementation.

  • Recursion Depth: Recursive implementations can hit stack limits on deep trees; prefer iterative approaches for large datasets.

  • Inorder Traversal: Remember that an in-order traversal of a valid BST yields a sorted sequence, which is a common validation technique.

5

What is an AVL tree and how does it maintain balance?

An AVL tree is a self-balancing binary search tree (BST) in which the heights of the two child subtrees of every node differ by at most one. It preserves this height-balance invariant after insertions and deletions through local rotations, giving logarithmic-time search, insertion, and deletion.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Ideas

For each node, define the balance factor as:

balance factor = height(left subtree) - height(right subtree)

An AVL tree permits balance factors of -1, 0, or 1. A factor greater than 1 means the node is left-heavy; a factor less than -1 means it is right-heavy.

Related definitions:

  • Binary tree: Each node has at most two children; values need not be ordered.

  • Binary search tree (BST): Smaller keys are in the left subtree and larger keys are in the right subtree, subject to a stated duplicate-handling policy.

  • Complete tree: Every level except possibly the last is full, and the last level is filled from left to right.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has two children, and all leaves have the same depth.

  • Balanced tree: A general term for a tree whose height grows logarithmically with its number of nodes. An AVL tree specifically enforces a height difference of at most one at every node.

Maintaining Balance

Insertions and deletions first follow the ordinary BST rules. Heights and balance factors are then updated while the recursion unwinds, or while an explicit stack unwinds in an iterative implementation.

Case Balance condition Rebalancing operation
Left-Left (LL) BF(node) > 1 and BF(left) >= 0 Rotate right around node
Left-Right (LR) BF(node) > 1 and BF(left) < 0 Rotate left around the left child, then right around node
Right-Right (RR) BF(node) < -1 and BF(right) <= 0 Rotate left around node
Right-Left (RL) BF(node) < -1 and BF(right) > 0 Rotate right around the right child, then left around node

A rotation changes a few parent-child links, preserves BST ordering, and restores balance at the affected nodes. During deletion, a node with two children may first be replaced by its inorder successor or predecessor.

Example walkthrough:

  1. Insert 10; it becomes the root.

  2. Insert 20; it becomes the right child of 10, and the tree remains balanced.

  3. Insert 30; it becomes the right child of 20. The balance factor at 10 becomes -2, and its right child is not left-heavy, so this is an RR case.

  4. Rotate left around 10. The root becomes 20, with left child 10 and right child 30; all balance factors are restored.

Complexity

Let n be the number of nodes and h the height measured in edges. For an AVL tree, h = O(log n).

Operation Best case Average case Worst case Auxiliary space Reason
Search O(1) O(log n) O(log n) O(1) iterative; O(h) = O(log n) recursive Search follows one path, and AVL height is logarithmically bounded
Insertion O(1) O(log n) O(log n) O(h) = O(log n) recursive or with an explicit stack; O(1) iterative only with parent pointers The search path is logarithmic, and each rotation changes only a constant number of links
Deletion O(1) O(log n) O(log n) O(h) = O(log n) recursive or with an explicit stack; O(1) iterative only with parent pointers The search path is logarithmic, with constant-time rotations and at most one successor or predecessor lookup
Inorder traversal O(n) O(n) O(n) O(h) recursive or with an explicit stack; O(1) with Morris traversal Every node is visited exactly once

These space figures are auxiliary and exclude the input tree. They also exclude a returned inorder result; including that output adds O(n) space.

Common Pitfalls

  • Height convention: Mixing edge counts and node counts causes off-by-one errors. The convention used here gives an empty tree height -1 and a leaf height 0.

  • Balance-factor sign: A positive factor means left-heavy; a negative factor means right-heavy.

  • Rotation order: LR requires a left rotation followed by a right rotation; RL requires the reverse.

  • Stale metadata: Update the lower node before the new subtree root after every rotation.

  • Duplicate keys: Define a consistent policy, such as ignoring duplicates, storing counts, or keeping duplicates on one side.

  • Mutation: Rotations mutate links, so an API that promises not to mutate its input must copy affected nodes.

  • Numeric limits: In fixed-width languages, use sufficiently wide key and counter types and avoid overflow.

  • Edge cases: Empty and single-node trees, negative keys, duplicates, deletion from an empty tree, and already sorted input must be handled deliberately.

  • Interview follow-ups: Be ready to explain the four rotation cases, prove that rotations preserve BST ordering, and compare AVL trees with red-black trees.

6

How does a Red-Black Tree maintain balance?

A Red-Black Tree is a self-balancing binary search tree that assigns colors to nodes and uses rotations and recoloring to constrain its height. These invariants guarantee that searching, insertion, and deletion take O(log n) time in the worst case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Tree Types and Invariants

A Red-Black Tree is a binary search tree with additional rules:

  • Every node is either red or black.

  • The root is black.

  • Every None leaf, often called a NIL leaf, is treated as black.

  • A red node cannot have a red child.

  • Every path from a node to its descendant NIL leaves contains the same number of black nodes.

The last rule is called black-height. Together, the rules ensure that the tree’s height is at most 2 log2(n + 1).

Structure Defining property
Binary tree Each node has at most two children
Binary search tree Keys satisfy the left/right ordering invariant
Complete tree All levels are full except possibly the last, which is filled left to right
Full tree Every node has either zero or two children
Perfect tree Every internal node has two children and all leaves have equal depth
Balanced tree Height is kept within a defined logarithmic bound
Red-Black Tree A binary search tree using color invariants to maintain balance

A Red-Black Tree is not necessarily complete, full, or perfect.

Balancing and Complexity

Let n be the number of nodes and h the tree height, measured in edges. An empty tree has height -1, and a leaf has height 0.

Operation Best time Average time Worst time Auxiliary space
Search O(1) O(log n) O(log n) O(1)
Insert O(log n) O(log n) O(log n) O(1) for iterative fix-up
Delete O(log n) O(log n) O(log n) O(1) with an iterative implementation
In-order traversal O(n) O(n) O(n) O(h) stack, excluding output

Search follows one root-to-leaf path, and a Red-Black Tree guarantees h = O(log n). The tree itself occupies O(n) space. Auxiliary-space figures exclude both the input values and the stored tree. A recursive traversal would also require O(h) recursion-stack space; an iterative traversal uses an explicit stack of the same size.

Insertion Mechanics

Insertion first places the new node in its binary-search-tree position and colors it red. A red node cannot have a red parent, so a red-red violation may require:

  1. Recoloring the parent, uncle, and grandparent when the uncle is red.

  2. Rotating and recoloring when the uncle is black, converting a straight or zig-zag configuration into a valid one.

For example, inserting 10, 20, and 30 produces:

  1. 10 becomes the black root.

  2. 20 is inserted as its red right child.

  3. 30 creates a red-red violation on the right.

  4. Because the uncle is black (NIL) and the nodes form a straight right-right line, recoloring and a single left rotation at 10 make 20 the black root with red children.

Code Example

from typing import Literal

Color = Literal["red", "black"]


class TreeNode:
    def __init__(self, val: int) -> None:
        self.val = val
        self.left: TreeNode | None = None
        self.right: TreeNode | None = None
        self.parent: TreeNode | None = None
        self.color: Color = "red"


class RedBlackTree:
    def __init__(self) -> None:
        self.root: TreeNode | None = None

    def insert(self, value: int) -> None:
        """Insert a unique integer while preserving Red-Black invariants."""
        new_node = TreeNode(value)

        if self.root is None:
            self.root = new_node
            self.root.color = "black"
            return

        current = self.root
        while current is not None:
            if value == current.val:
                raise ValueError("Duplicate values are not supported")

            if value < current.val:
                if current.left is None:
                    current.left = new_node
                    new_node.parent = current
                    break
                current = current.left
            else:
                if current.right is None:
                    current.right = new_node
                    new_node.parent = current
                    break
                current = current.right

        self._fix_insert(new_node)

    def _rotate_left(self, node: TreeNode) -> None:
        promoted = node.right
        if promoted is None:
            return

        node.right = promoted.left
        if promoted.left is not None:
            promoted.left.parent = node

        promoted.parent = node.parent
        if node.parent is None:
            self.root = promoted
        elif node is node.parent.left:
            node.parent.left = promoted
        else:
            node.parent.right = promoted

        promoted.left = node
        node.parent = promoted

    def _rotate_right(self, node: TreeNode) -> None:
        promoted = node.left
        if promoted is None:
            return

        node.left = promoted.right
        if promoted.right is not None:
            promoted.right.parent = node

        promoted.parent = node.parent
        if node.parent is None:
            self.root = promoted
        elif node is node.parent.right:
            node.parent.right = promoted
        else:
            node.parent.left = promoted

        promoted.right = node
        node.parent = promoted

    def _fix_insert(self, node: TreeNode) -> None:
        while node.parent is not None and node.parent.color == "red":
            parent = node.parent
            grandparent = parent.parent
            if parent is None or grandparent is None:
                break

            if parent is grandparent.left:
                uncle = grandparent.right

                if uncle is not None and uncle.color == "red":
                    parent.color = "black"
                    uncle.color = "black"
                    grandparent.color = "red"
                    node = grandparent
                else:
                    if node is parent.right:
                        node = parent
                        self._rotate_left(node)
                        parent = node.parent
                        grandparent = parent.parent if parent else None

                    if parent is not None and grandparent is not None:
                        parent.color = "black"
                        grandparent.color = "red"
                        self._rotate_right(grandparent)
            else:
                uncle = grandparent.left

                if uncle is not None and uncle.color == "red":
                    parent.color = "black"
                    uncle.color = "black"
                    grandparent.color = "red"
                    node = grandparent
                else:
                    if node is parent.left:
                        node = parent
                        self._rotate_right(node)
                        parent = node.parent
                        grandparent = parent.parent if parent else None

                    if parent is not None and grandparent is not None:
                        parent.color = "black"
                        grandparent.color = "red"
                        self._rotate_left(grandparent)

        if self.root is not None:
            self.root.color = "black"

    def values_in_order(self) -> list[int]:
        """Return keys in sorted order using iterative in-order traversal."""
        result: list[int] = []
        stack: list[TreeNode] = []
        current = self.root

        while current is not None or stack:
            while current is not None:
                stack.append(current)
                current = current.left

            current = stack.pop()
            result.append(current.val)
            current = current.right

        return result


tree = RedBlackTree()
tree.insert(10)
tree.insert(20)
tree.insert(30)

print(tree.values_in_order())                  # [10, 20, 30]
print(tree.root.color if tree.root else None) # black

Common Pitfalls

  • Do not assume every Red-Black Tree is complete, full, or perfect.

  • Treat None leaves as black when checking black-height.

  • State the duplicate-key policy explicitly; this implementation rejects duplicates.

  • Include recursion-stack space when using recursive traversals.

  • Do not confuse black-height with ordinary height: black-height counts black nodes, while ordinary height counts edges.

  • Common follow-up questions cover implementing deletion, validating all invariants, comparing Red-Black Trees with AVL trees, and explaining why an in-order traversal produces sorted keys.

7

How does an AVL tree differ from a B-tree?

An AVL tree is a self-balancing binary search tree that stores one key per node, while a B-tree is a multiway search tree designed for block-based storage, allowing each node to store many keys and children. Both provide efficient ordered lookup, but they optimize for different workloads.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Property AVL tree B-tree
Node structure Binary: at most two children Multiway: can have many children
Keys per node Usually one Many
Primary goal Minimize tree height for in-memory lookups Minimize storage-block accesses for large datasets
Balancing method Rotations after insertions or deletions Splitting overflowing nodes and merging underflowing nodes
Leaf depth Leaves may have different depths All leaves are at the same depth
Typical implementation Linked nodes and pointers Contiguous, disk-friendly nodes or pages
Common use case In-memory dictionaries and ordered sets Databases and file systems

A conventional B-tree is therefore not simply a balanced binary tree. Its high fan-out allows it to have fewer levels, which is valuable when accessing data from disks or SSDs.

How Balancing Works

  • AVL tree: Every node maintains a balance factor based on the heights of its left and right subtrees, commonly restricted to -1, 0, or 1.

  • Insertion or deletion: If the balance factor becomes invalid, the tree performs one or more rotations to restore balance.

  • B-tree: Each node has a maximum capacity. Insertion splits an overflowing node, while deletion may borrow from a sibling or merge nodes.

  • Occupancy rules: B-tree implementations commonly require nodes to remain at least half full, except possibly the root.

Both structures maintain logarithmic height under their respective node-size constraints. A B-tree generally has fewer levels because its fan-out is greater; an AVL tree has more levels but only one key per node.

Complexity

Let n be the number of keys, h the tree height, and m the maximum number of children per B-tree node. The B-tree bounds below assume a fixed maximum fan-out m.

Operation Best Average Worst Reason
AVL search O(1) O(log n) O(log n) Balance keeps height logarithmic; a key may be found at the root
AVL insertion or deletion O(log n) O(log n) O(log n) Search and rebalancing both follow a logarithmic path
B-tree search O(1) O(log n) O(log n) A search visits O(log_m n) nodes and performs work within each node
B-tree insertion or deletion O(log n) O(log n) O(log n) Splits or merges can occur along one root-to-leaf path

For a B-tree with variable fan-out, the height is O(log_m n); for fixed m, this is O(log n). A search within a node adds that node’s key-comparison cost.

The total stored space for either structure is O(n), including the nodes that hold the input keys. An iterative search uses O(1) auxiliary space. A recursive search uses O(h) call-stack space: O(log n) for an AVL tree and O(log_m n) for a B-tree.

Practical Trade-offs

  • AVL trees are effective when data fits in memory and operations are frequent, such as in-memory indexes, caches, and ordered dictionaries.

  • B-trees are effective for large persistent datasets because one node can correspond to a storage page, reducing expensive I/O operations.

  • B-trees have larger nodes and more complex update logic.

  • AVL trees have simpler node structures but may require more pointer traversals because each node contains only one key.

  • Many database indexes use B+ trees, a B-tree variant that stores records or pointers only in leaf nodes and links leaves for efficient range scans.

Common Pitfalls and Interview Tips

  • Do not describe a B-tree as merely another name for a binary tree; its defining feature is multiway branching.

  • Do not confuse a balanced tree with a perfect tree. A perfect tree also has all leaves at the same depth and all internal nodes with exactly two children.

  • Mention that AVL balancing uses rotations, whereas B-tree balancing uses splits, borrows, and merges.

  • A common follow-up asks which is better for a database: the practical answer is usually a B-tree or B+ tree because storage-block access dominates performance.

  • Another follow-up asks about range queries: AVL in-order traversal is simple, while B+ trees are generally preferred in databases because linked leaves make sequential range access efficient.

8

How does a Fenwick Tree improve algorithm design?

A Fenwick Tree, or Binary Indexed Tree, improves algorithm design by replacing repeated O(n) prefix-sum scans with O(log n) updates and queries. It is especially effective when values change frequently and prefix or range sums are queried often.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

For a 1-indexed Fenwick Tree, each entry at index i stores the sum of a block whose length is determined by its lowest set bit:

lowbit(i) = i & -i

Index lowbit Stored range
1 1 [1, 1]
2 2 [1, 2]
3 1 [3, 3]
4 4 [1, 4]
5 1 [5, 5]

An update visits i, i + lowbit(i), and so on. A prefix query visits i, i - lowbit(i), and so on. These paths contain only O(log n) indexes.

A Fenwick Tree is not a binary search tree or a conventional binary tree. It stores aggregate values rather than TreeNode objects.

Algorithm Comparison

Approach Point update Prefix sum Space When to use
Plain array O(1) O(n) O(n) Updates are rare and values are queried infrequently
Fenwick Tree O(log n) O(log n) O(n) Prefix sums or range sums are frequent
Segment tree O(log n) O(log n) O(n) Queries also need minima, maxima, or other associative operations

For an inclusive range:

range_sum(left, right) = prefix_sum(right) - prefix_sum(left - 1)

A Fenwick Tree is often preferable to a segment tree for addition or subtraction because it is simpler and usually has lower constant overhead.

Complexity

Let n be the number of elements and h = floor(log2 n) + 1 be the maximum number of indexing levels visited by an operation. These bounds assume constant-time arithmetic.

  • Point update: O(1) best case, such as updating the final index; O(h) = O(log n) average and worst case.

  • Prefix query: O(1) best case, such as querying a prefix ending at a power of two; O(h) = O(log n) average and worst case.

  • Range query: O(1) best case and O(h) = O(log n) average and worst case because it combines two prefix queries.

  • Construction: O(n) in all cases when all values are known and a linear build is used.

  • Storage: O(n) for the Fenwick Tree.

  • Auxiliary space during an operation: O(1); there is no recursion stack.

  • The supplied input sequence is not included in the Fenwick Tree’s O(n) storage; including it does not change the total asymptotic space.

Walkthrough

For the array [3, 2, -1, 4, 5], a prefix query through index 5 proceeds as follows:

  1. Read tree[5], which stores the value at index 5: 5.

  2. Move to 5 - lowbit(5) = 4.

  3. tree[4] stores the sum of indices 1 through 4: 3 + 2 - 1 + 4 = 8.

  4. The result is 5 + 8 = 13.

Negative values and duplicates require no special handling because the structure only uses addition and subtraction.

Common Pitfalls

  • Indexing confusion: Standard Fenwick Trees use 1-based storage; a prefix query through index 0 should return 0.

  • Empty input: There is no nonempty range to query, although the tree can still be created safely.

  • One element: Point updates and prefix or range queries behave normally.

  • Incorrect update direction: Updates move upward with i += lowbit(i), while prefix queries move downward with i -= lowbit(i).

  • Mutating the input: Keep aggregate state separate from the source sequence when the source must remain unchanged.

  • Choosing the wrong structure: Use a segment tree for non-additive operations such as range minimum, maximum, or product.

  • Common follow-up: Interviewers often ask for an online inversion counter, where each inserted value is queried against a Fenwick Tree to count smaller preceding elements.

9

How does a Segment Tree differ from a traditional binary tree?

A Segment Tree is a specialized binary tree that stores summaries—such as sums, minimums, or maximums—for contiguous array ranges. Unlike a conventional binary tree organized around individual values or keys, it efficiently supports range queries and updates while retaining root-to-leaf access to individual elements.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Key Concepts

Each Segment Tree node represents an interval:

  • Leaves correspond to individual array elements.

  • Internal nodes store an aggregate computed from their children.

  • A point update changes one leaf and recalculates its ancestors.

  • A range query combines up to O(log n) disjoint stored intervals.

  • Lazy propagation supports efficient range updates by postponing propagation to child nodes until necessary.

Relevant tree definitions distinguish several properties:

  • Binary tree: Every node has at most two children, with no ordering requirement.

  • Binary search tree (BST): Keys in a node’s left subtree are smaller and keys in its right subtree are larger, under the usual no-duplicates convention.

  • Complete tree: Every level is full except possibly the last, which is filled from left to right.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has two children and all leaves are at the same depth.

  • Balanced tree: Its height is O(log n), preventing a fully skewed shape.

A Segment Tree is not a BST: its ordering comes from represented intervals rather than comparisons between stored keys. A standard recursive midpoint-split Segment Tree is balanced. It is not necessarily complete for a non-power-of-two number of elements; padding to the next power of two produces a complete, perfect tree.

Usage and Efficiency Comparison

Property Segment Tree Traditional binary tree or BST
Primary purpose Range queries and updates Point lookup, insertion, deletion, and traversal
Node meaning Summary of a fixed array interval Usually one stored value or key
Find a value by traversal O(log n) in a standard balanced Segment Tree O(n) for an unstructured binary tree; O(log n) for a balanced BST; O(n) for a skewed BST
Arbitrary range aggregate O(log n) Usually O(n) without additional augmentation
Point update O(log n) O(h), where h is tree height
Build O(n) O(n) to assemble a known shape; inserting n keys costs O(n log n) in a balanced BST and O(n²) in the worst case for an ordinary unbalanced BST
Storage O(n) O(n)
Common shapes Usually balanced; often complete when padded Any shape unless balancing is enforced

A Segment Tree is not universally better. A prefix-sum array provides O(1) prefix and additive range queries with O(n) space for static values. A sparse table uses O(n log n) preprocessing and space but answers static minimum or maximum queries in O(1). A Fenwick tree uses O(n) space and supports point updates and prefix or range-sum queries in O(log n) when those operations are sufficient.

Small Example

For [1, 2, 3, 4, 5], suppose the root represents indices [0, 4], its left child represents [0, 2], and its right child represents [3, 4].

  1. Querying [0, 3] uses the complete left subtree, whose sum is 6, and the leaf at index 3, whose value is 4. The result is 10.

  2. Updating index 2 from 3 to 10 changes that leaf, the left subtree sum to 13, and the root sum to 22.

  3. Querying [0, 3] again returns 13 + 4 = 17.

Complexity

For n elements and a standard balanced Segment Tree:

  • Build: O(n) best, average, and worst-case time because every leaf and internal node is created once.

  • Point update: O(log n) best, average, and worst-case time because one root-to-leaf path is recalculated.

  • Range query: O(1) best case when the requested range matches a stored node, and O(log n) average and worst case because only boundary paths and stored summaries are processed.

  • Stored structure: O(n) space because it contains O(n) nodes.

  • Recursive auxiliary space: O(h) = O(log n) for the build, query, and update call stacks because recursion follows the tree height. These figures exclude the input; including the input and stored tree still gives O(n) total space.

Common Pitfalls

  • Empty input: Define whether an empty tree is permitted; reject it or return a documented neutral result.

  • Single element: Build, query, and update operate in O(1) time and space.

  • Duplicates and negative values: These are supported naturally by sum-based Segment Trees.

  • Range conventions: State whether ranges are inclusive or exclusive to prevent off-by-one errors.

  • Range updates: Updating every affected leaf is not O(log n) for a large range; lazy propagation provides the standard O(log n) approach.

  • Tree terminology: Do not assume every Segment Tree is complete, full, perfect, or balanced.

  • Common follow-up: Interviewers often ask about lazy propagation, non-power-of-two sizes, Fenwick-tree alternatives, and how to support other aggregates such as minima or maxima.

10

How does a splay tree perform rotation-based splaying?

A splay tree is a self-adjusting binary search tree (BST) that moves a recently accessed node to the root using rotations. Splaying preserves the BST property and gives amortized (O(log n)) access time over a sequence of operations, although one individual operation can take (O(n)).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How the Splay Operation Works

The splay operation uses one of three rotation patterns, depending on the node’s relationship with its parent and grandparent:

  • Zig: The node has only a parent. One rotation moves it above its parent.

  • Zig-zig: The node and its parent are both left children, or both right children. Rotate the grandparent first, then the parent. This is important for maintaining the amortized bound.

  • Zig-zag: The node and its parent are on opposite sides. Rotate the node above its parent, then rotate it above its grandparent.

A rotation moves one node upward while preserving the tree’s inorder sequence, so all BST search properties remain valid.

Small Example

Consider this BST:

10
      /  \
     5    15
    / \
   3   7

Accessing 3 follows the path 10 → 5 → 3. Because this is a zig-zig case:

  1. Rotate right around 10, making 5 the subtree root.

  2. Rotate right around 5, making 3 the subtree root.

  3. The final tree begins with 3 as its root.

The inorder traversal remains 3, 5, 7, 10, 15; only the shape changes.

Complexity

For (n) nodes and tree height (h):

Operation Best case Average or amortized case Worst case
Search plus splay (O(1)) (O(log n)) amortized (O(n))
One rotation (O(1)) (O(1)) (O(1))
  • A single splay operation takes (O(h)), where (h) can be (O(n)) for a skewed tree.

  • The standard amortized analysis gives (O(log n)) per operation over a sequence of accesses.

  • The implementation below uses no recursion: auxiliary space is (O(1)).

  • The input tree itself occupies (O(n)) space; the parent pointers are bookkeeping and do not change the asymptotic bound.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None
    parent: TreeNode | None = None


def _rotate_right(node: TreeNode) -> TreeNode:
    """Rotate node downward, promoting its left child."""
    promoted = node.left
    if promoted is None:
        raise ValueError("Cannot rotate right without a left child")

    parent = node.parent

    node.left = promoted.right
    if promoted.right is not None:
        promoted.right.parent = node

    promoted.right = node
    promoted.parent = parent

    if parent is not None:
        if parent.left is node:
            parent.left = promoted
        else:
            parent.right = promoted

    node.parent = promoted
    return promoted


def _rotate_left(node: TreeNode) -> TreeNode:
    """Rotate node downward, promoting its right child."""
    promoted = node.right
    if promoted is None:
        raise ValueError("Cannot rotate left without a right child")

    parent = node.parent

    node.right = promoted.left
    if promoted.left is not None:
        promoted.left.parent = node

    promoted.left = node
    promoted.parent = parent

    if parent is not None:
        if parent.left is node:
            parent.left = promoted
        else:
            parent.right = promoted

    node.parent = promoted
    return promoted


def splay(root: TreeNode | None, value: int) -> TreeNode | None:
    """Access value and move its node to the root."""
    target = root

    # Find the node using BST ordering.
    while target is not None and target.val != value:
        if value < target.val:
            target = target.left
        else:
            target = target.right

    if target is None:
        return root  # Value is absent; leave the tree unchanged.

    while target.parent is not None:
        parent = target.parent
        grandparent = parent.parent

        if grandparent is None:
            # Zig
            if parent.left is target:
                _rotate_right(parent)
            else:
                _rotate_left(parent)

        elif parent is grandparent.left and target is parent.left:
            # Zig-zig
            _rotate_right(grandparent)
            _rotate_right(parent)

        elif parent is grandparent.right and target is parent.right:
            # Zig-zig
            _rotate_left(grandparent)
            _rotate_left(parent)

        else:
            # Zig-zag
            if target is parent.left:
                _rotate_right(parent)
            else:
                _rotate_left(parent)

            # The target now has the grandparent as its parent.
            if target.parent is not None and target.parent.left is target:
                _rotate_right(target.parent)
            else:
                _rotate_left(target.parent)

    return target


root = TreeNode(10)
root.left = TreeNode(5, parent=root)
root.right = TreeNode(15, parent=root)
root.left.left = TreeNode(3, parent=root.left)
root.left.right = TreeNode(7, parent=root.left)

new_root = splay(root, 3)
print(new_root.val, new_root.right.val, new_root.right.right.val)
# Expected output: 3 5 10

Common Pitfalls and Interview Tips

  • Incorrect rotation order: In zig-zig, rotate the grandparent before the parent; doing it in the other order can lose the amortized guarantee.

  • Broken parent links: Every rotation must update the promoted node’s parent, the demoted node’s parent, and the old parent’s child pointer.

  • Empty tree: splay(None, value) safely returns None.

  • Single-node tree: The node is already the root, so no rotation occurs.

  • Missing value: The implementation leaves the tree unchanged.

  • Negative values: Ordinary integer comparisons work normally.

  • Duplicate keys: Use a consistent BST policy; the example assumes distinct keys.

  • Already sorted input: It is still a valid tree, but individual operations may initially be (O(n)); amortized performance is achieved over subsequent operations.

  • Cycles or disconnected structures: These do not apply to one valid binary tree. The implementation assumes a single properly connected tree with no parent-pointer cycles.

  • Common follow-up: Explain why splay trees do not need to remain height-balanced after every operation, and distinguish their amortized (O(log n)) bound from worst-case (O(n)) behavior.

11

What is the concept and structure of a ternary tree?

A ternary tree is a rooted tree data structure in which each node has at most three children. Its child positions are commonly stored as left, middle, and right, allowing three-way branching while preserving a hierarchy.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Concept

A ternary tree contains nodes connected by parent-child relationships. The root has no parent, while every other node has exactly one parent. Each node may have zero, one, two, or three children.

When the child positions are ordered, they are commonly named:

  • left: the first child

  • middle: the second child

  • right: the third child

Not every ternary tree requires ordered children, but ordered positions are useful when traversal order matters. Ternary trees can represent expression trees with three operands, game states with several possible moves, and hierarchical categories.

A ternary tree is not automatically a search tree. A conventional ternary search tree (TST) uses three child pointers:

  • left: keys smaller than the node’s key

  • middle or equal: keys equal to the node’s key

  • right: keys greater than the node’s key

Tree Family Distinctions

Structure Definition
Binary tree Every node has at most two children.
Binary search tree A binary tree with ordering rules between a node and its left and right subtrees.
Complete binary tree All levels are full except possibly the last, which is filled from left to right.
Full binary tree Every node has either zero or two children.
Perfect binary tree Every internal node has two children and all leaves have the same depth.
Balanced tree At every node, the heights of the child subtrees differ by at most one under the common height-balanced definition.
Full ternary tree Every node has either zero or three children.
Complete ternary tree All levels are full except possibly the last, which is filled in child order.
Perfect ternary tree Every internal node has three children and all leaves have the same depth.

These properties are independent. For example, a complete tree need not be perfect, and a balanced tree need not be complete.

Structure Example

Consider this tree:

Node left middle right
1 2 3 4
2 5 6 7
3 — — —
4 — — —
5 — — —
6 — — —
7 — — —

A preorder traversal visits each node before its children:

  1. Visit root 1.

  2. Descend to 1’s left child 2 and visit it.

  3. Visit 2’s children in order: 5, 6, and 7.

  4. Return to 1 and visit its middle child 3.

  5. Visit 1’s right child 4.

The preorder sequence is 1, 2, 5, 6, 7, 3, 4. A level-order traversal visits nodes by depth and produces 1, 2, 3, 4, 5, 6, 7.

Complexity

For n nodes and tree height h:

Operation Time Auxiliary space Reason
Accessing a known child O(1) O(1) The child is referenced directly.
Searching an unstructured ternary tree O(n) O(1) Any node may need to be examined.
Searching an ordered ternary search tree O(h) O(1) Ordering determines which child subtree can contain the target.
DFS traversal O(n) O(h) Every node is visited once, and the active path or stack has at most O(h) entries.
BFS traversal O(n) O(w) The queue stores up to O(w) nodes, where w is the maximum width.

Auxiliary space excludes the input tree itself. Including the tree’s storage, total space is O(n) for either traversal. Height here counts edges: an empty tree has height -1, a leaf has height 0, a skewed tree has h = O(n), and a balanced tree has h = O(log n).

Common Pitfalls

  • Confusing “at most three children” with “exactly three children.”

  • Assuming an ordinary ternary tree enforces value ordering.

  • Using the conventional TST meaning of middle without stating that the tree is a search tree.

  • Visiting children in an unexpected order when the child positions are ordered.

  • Mixing height conventions; use edges when the empty tree has height -1.

  • Treating an empty or single-node tree as malformed; both are valid.

  • Assuming ordinary ternary trees prohibit duplicate or negative values.

  • Treating a disconnected structure or one containing a cycle as a tree; those are respectively a forest or a graph.

12

When is a lazy segment tree preferable to a regular segment tree?

A lazy segment tree maintains range aggregates while postponing updates to child nodes through a lazy marker. It is preferable to a regular segment tree when both range updates and range queries are frequent.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

A segment tree is a balanced binary tree representing array intervals. Each node stores an aggregate such as the sum of its interval.

With a regular segment tree, a range update must generally update every affected leaf, taking up to O(n) time. A lazy segment tree records a pending update at a fully covered node and propagates it to its children only when a later operation needs to descend into that node.

The key invariant is:

  • The node’s stored sum already includes its pending lazy update.

  • Its children may not yet include that update.

  • Before descending into children, the pending update is pushed to them.

Operations

Ranges are zero-based and inclusive.

  1. Build: Calculate each node’s sum from its children.

  2. Range add: If a node is fully covered, update its sum and lazy marker. Otherwise, push pending work, update the relevant children, and recompute the node’s sum.

  3. Range sum: If a node is fully covered, return its sum. Otherwise, push pending work and combine the results from the relevant children.

  4. Push: Apply a node’s lazy marker to both children and clear the marker.

For [1, 2, 3, 4, 5], adding 10 to indices [1, 3] changes the array to [1, 12, 13, 14, 5]. The relevant leaves receive the update, and ancestor sums are recomputed to produce a total of 45.

Complexity

Operation Best Average Worst Reason
Build O(n) O(n) O(n) Every node is initialized once
Range add O(1) O(log n) O(log n) A full-tree update is O(1); other ranges follow O(log n) boundary paths
Range sum O(1) O(log n) O(log n) A full-tree query returns the root; other ranges visit O(log n) nodes

Space complexity: O(n), including the segment-tree arrays. The recursion stack uses O(log n) because the tree is balanced. The original input array is not counted as auxiliary space.

Lazy vs. Regular Segment Tree

Requirement Regular Segment Tree Lazy Segment Tree
Point update and range query Simpler; both O(log n) Works but lazy propagation is unnecessary
Range update and range query Range update may require O(n) work Both operations are O(log n)
Memory O(n) O(n)
Best use Static aggregates or point updates Frequent range additions with range queries

Common examples include adding a value to every salary in a department or incrementing a subarray while frequently querying subarray sums.

Common Pitfalls

  • Forgetting to push before descending into a node’s children.

  • Forgetting to pull after modifying children, leaving an incorrect ancestor sum.

  • Mixing inclusive and exclusive ranges; the ranges in this answer use inclusive endpoints.

  • Assuming the lazy marker is excluded from the node’s stored sum.

  • Testing only positive updates: negative values are fully supported, while duplicate or sorted values are irrelevant to range sums.

  • Python integers do not overflow, although fixed-width integer overflow must be considered in languages such as Java or C++.

13

How does a treap combine binary search tree and heap properties?

A treap is a binary tree that satisfies both binary search tree (BST) ordering and heap ordering. Keys determine the left-to-right placement, while random priorities determine the tree’s shape, giving an expected height of (O(log n)).

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Properties

For a max-priority treap, every node’s priority is at least as large as the priorities of its children.

  • BST property: If a node has key x, smaller keys belong in its left subtree and larger keys in its right subtree.

  • Heap property: A node’s priority is greater than or equal to its children’s priorities.

  • Inorder traversal: Visiting nodes in left-root-right order produces the keys in sorted order.

  • Randomized balance: Independently generated random priorities make a skewed tree unlikely.

The treap is the unique binary tree formed by combining a sorted sequence of keys with a sequence of distinct priorities. Rotations can repair the heap property without changing the BST order.

A treap is not necessarily complete, full, perfect, or perfectly balanced. Those are separate structural properties:

  • Complete: Every level except possibly the last is full, and the last level is filled from the left.

  • Full: Every node has either zero or two children.

  • Perfect: Every internal node has two children, and all leaves have the same depth.

  • Balanced: The heights of a node’s child subtrees differ by at most one, using the height convention stated below.

How Insertion Works

Insertion first places a node using ordinary BST rules. If its priority violates the heap property, rotations restore it:

  1. If a right child has a higher priority, rotate left.

  2. If a left child has a higher priority, rotate right.

  3. Continue until the priority heap property is restored.

Both rotations preserve the inorder sequence, so the BST ordering remains valid.

For example, using maximum priorities:

  1. Insert 50 with priority 8; it becomes the root.

  2. Insert 30 with priority 5; it becomes the left child of 50.

  3. Insert 70 with priority 9; it is attached on the right, then a left rotation makes 70 the root and moves 50 to its left.

A duplicate key can be ignored, replaced, or given a separate policy. The implementation below ignores it.

Complexity

Let n be the number of nodes and h the tree height, counting edges; an empty tree has height -1.

Operation Best Average / Expected Worst Auxiliary space
Search (O(1)) (O(log n)) (O(n)) (O(h)) recursive; (O(1)) iterative
Insert (O(1)) (O(log n)) (O(n)) (O(h)), including recursion stack
Delete (O(1)) (O(log n)) (O(n)) (O(h)), including recursion stack

The average bounds assume independent random priorities and ordinary insertion sequences. A fixed or predictable priority sequence can be arranged adversarially to produce a skewed tree.

The stored treap occupies (O(n)) space. The operation complexities above exclude stored nodes but include the recursion stack. In the example, the values and priorities lists additionally occupy (O(n)) input space.

Code Example

from __future__ import annotations

from dataclasses import dataclass
from random import sample


@dataclass
class TreeNode:
    val: int
    priority: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def rotate_right(root: TreeNode) -> TreeNode:
    """Rotate a node right to promote its left child."""
    left_child = root.left
    if left_child is None:
        return root

    root.left = left_child.right
    left_child.right = root
    return left_child


def rotate_left(root: TreeNode) -> TreeNode:
    """Rotate a node left to promote its right child."""
    right_child = root.right
    if right_child is None:
        return root

    root.right = right_child.left
    left_child = right_child.left
    right_child.left = root
    return right_child


def insert(
    root: TreeNode | None,
    value: int,
    priority: int,
) -> TreeNode:
    """Insert a unique value using BST placement and max-heap rotations."""
    if root is None:
        return TreeNode(val=value, priority=priority)

    if value < root.val:
        root.left = insert(root.left, value, priority)
        if root.left.priority > root.priority:
            root = rotate_right(root)

    elif value > root.val:
        root.right = insert(root.right, value, priority)
        if root.right.priority > root.priority:
            root = rotate_left(root)

    # Duplicate values are ignored and retain the original priority.
    return root


def inorder(root: TreeNode | None) -> list[int]:
    """Return the treap keys in sorted order using an explicit stack."""
    result: list[int] = []
    stack: list[TreeNode] = []
    current = root

    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()
        result.append(current.val)
        current = current.right

    return result


values = [50, 30, 70, 20, 40, 60, 80]
priorities = sample(range(1, 100), len(values))
root: TreeNode | None = None

for value, priority in zip(values, priorities):
    root = insert(root, value, priority)

print(inorder(root))
# Expected output: [20, 30, 40, 50, 60, 70, 80]

Common Pitfalls

  • Confusing key and priority order: Keys control BST placement; priorities control heap balance. They are separate values.

  • Using predictable priorities: A fixed priority order can allow an adversary to construct a height-(O(n)) treap.

  • Breaking BST order during rotations: A correct rotation preserves the inorder sequence.

  • Ignoring duplicates: Define whether duplicates are ignored, replaced, counted, or stored separately.

  • Overlooking recursion depth: The recursive implementation assumes the height remains below Python’s recursion limit, approximately 1000. An iterative implementation is safer for adversarial or unusually large trees.

  • Ignoring edge cases: The code handles an empty tree, one element, negative values, and duplicate keys. Random priorities make ordinary insertions produce a balanced shape in expectation, but do not guarantee a particular tree structure.

14

What is a balanced binary tree?

A balanced binary tree is a binary tree in which, at every node, the heights of the left and right subtrees differ by at most one. This balance prevents the tree from becoming excessively deep and keeps tree-based operations efficient.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Definition

Using a height convention where an empty tree has height -1 and a leaf node has height 0, a tree is balanced when every node satisfies:

abs(height(left subtree) - height(right subtree)) <= 1

Balance is checked locally at every node, not only at the root.

  • Best-balanced structure: Leaves occupy the deepest level, and the tree is as compact as possible.

  • Height bound: A balanced tree containing n nodes has height O(log n).

  • Skewed tree: A tree resembling a linked list has height O(n) and is not balanced.

Binary Tree Type Comparisons

Tree type Defining property Relationship to balance
Binary tree Each node has at most two children May be balanced or unbalanced
Binary search tree (BST) Left subtree values are smaller and right subtree values are larger May be balanced or unbalanced
Complete binary tree Every level is full except possibly the last, which is filled from left to right Always balanced, since subtree heights differ by at most one
Full binary tree Every node has either zero or two children Can still be unbalanced
Perfect binary tree Every internal node has two children and all leaves are at the same depth Always balanced
Balanced binary tree Left and right subtree heights differ by at most one at every node Focuses on preventing excessive height

A perfect binary tree is therefore both complete and balanced, and every complete binary tree is balanced. A full binary tree is not necessarily balanced.

How Balance Is Maintained

Some binary search trees adjust their structure automatically whenever an insertion or deletion creates an imbalance:

  • AVL tree: Uses a strict height difference of at most one at every node. It generally offers faster lookups because it is more rigidly balanced.

  • Red-black tree: Uses color properties and rotations to maintain a looser balance. It generally supports efficient updates with fewer rotations.

  • Rotations: Restructure a small part of the tree while preserving its inorder sequence, which is essential for a BST.

  • Heights: Usually maintained separately or computed from child heights, allowing the tree to detect when a rotation is required.

The important distinction is between a data structure that merely has balanced shape and a self-balancing tree that maintains that shape automatically.

Complexity

For a balanced binary search tree containing n nodes and height h:

  • Search: Best case O(1) when the target is the root; average and worst case O(log n) because each comparison follows one root-to-leaf path.

  • Insertion and deletion: O(log n) worst case because the tree first searches for the position and may then perform a constant number of rotations.

  • Balancing work: Individual rotations take O(1) time, while locating the affected portion takes O(h).

  • Recursive auxiliary space: O(h), including the recursion stack. In a balanced tree, h = O(log n).

  • Iterative auxiliary space: O(1) for an iterative search; O(h) when an explicit stack is needed, depending on the algorithm.

  • Input storage: The tree itself occupies O(n) space and is not included in auxiliary-space measurements.

An unbalanced tree can require O(n) time for common operations and O(n) recursion space.

Common Pitfalls

  • Do not confuse balanced with complete, full, or perfect; these terms describe different properties.

  • Balance applies to every node, not just the root.

  • Height conventions differ. This answer counts edges, giving an empty tree height -1 and a leaf height 0.

  • A binary search tree is not automatically balanced; ordinary insertions can produce a skewed tree.

  • Interviewers may ask how rotations preserve the BST ordering, why balance improves lookup performance, or how AVL and red-black trees differ.

15

What are the trade-offs of using a binary search tree?

A binary search tree (BST) keeps keys in an ordered structure, enabling efficient searching, insertion, deletion, and sorted traversal when the tree remains reasonably balanced. Its main drawback is that an unbalanced BST can degrade from logarithmic operations to linear ones.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Behavior

A binary tree gives each node at most two children. In a BST, the ordering is:

  • Every key in the left subtree is smaller than the node’s key.

  • Every key in the right subtree is larger than the node’s key.

  • Both subtrees must independently satisfy the BST property.

Duplicate keys require an explicit policy, such as rejecting them, storing them consistently on one side, or maintaining a count at each node.

Advantages

  • Efficient dynamic operations: In a balanced BST, search, insertion, and deletion take O(log n) time without shifting array elements.

  • Sorted traversal: An inorder traversal produces keys in ascending order without sorting them separately.

  • Ordered queries: Finding a node’s predecessor, successor, floor, or ceiling takes O(log n) time in a balanced BST and O(n) in the worst case.

  • Range queries: Finding k keys between two bounds takes O(h + k) time, where h is tree height and k is the number of returned keys.

  • Natural hierarchy: Trees naturally represent hierarchical relationships and support operations such as finding the minimum or maximum key.

Disadvantages

  • Possible degeneration: Inserting sorted keys can create a skewed tree whose height is n - 1.

  • Worst-case performance: Operations on a skewed tree take O(n) time rather than O(log n).

  • Recursion-depth risk: Recursive operations may exceed Python’s default recursion limit of about 1,000.

  • Implementation complexity: Maintaining balance requires rotations or equivalent restructuring.

  • Memory overhead: Nodes require child references, and an object-based implementation has additional per-node overhead.

  • Poorer cache locality: Compared with a contiguous sorted array, pointer-based traversal may access memory less efficiently.

  • No universal duplicate policy: Correct behavior depends on how the application defines equal keys.

Complexity

Let n be the number of nodes, h the tree height, and w the maximum number of nodes at one level. Height counts edges: an empty tree has height -1, and a one-node tree has height 0.

Operation Best time Average time Worst time Auxiliary space Reason
Search O(1) O(log n) O(n) O(1) iterative; O(h) recursive Follows one root-to-leaf path; recursion retains the active path
Insert O(1) O(log n) O(n) O(1) iterative; O(h) recursive Finds an insertion position along one path
Delete O(1) O(log n) O(n) O(1) iterative; O(h) recursive Searches for the node and may locate a successor or predecessor
Full traversal O(n) O(n) O(n) O(h) DFS; O(w) BFS Every node is visited; DFS uses a path stack and BFS uses a level queue

The average cases assume uniformly random insertion order, which produces a roughly balanced tree in expectation. A self-balancing BST, such as an AVL or red-black tree, guarantees h = O(log n) and therefore avoids the linear worst case. In a skewed tree, h = O(n).

Auxiliary space excludes the input tree and any returned collection. A materialized traversal result uses an additional O(n) space. If the input tree is counted, total storage is O(n).

Tree Type Distinctions

Type Exact property
Binary tree Each node has at most two children; keys need not be ordered
Binary search tree Keys follow the left-smaller and right-larger ordering at every node
Complete tree Every level is full except possibly the last, whose nodes occupy the leftmost positions
Full tree Every node has either zero or two children
Perfect tree Every internal node has two children, and all leaves have the same depth
Balanced tree The precise invariant depends on the implementation; commonly it means height O(log n). The strict AVL definition requires subtree heights at every node to differ by at most one

Using the inline notation 8(3(1,6),10(∅,14)), where ∅ denotes a missing child, the traversal orders are:

  • Preorder: 8, 3, 1, 6, 10, 14

  • Inorder: 1, 3, 6, 8, 10, 14

  • Postorder: 1, 6, 3, 14, 10, 8

  • Level order: 8, 3, 10, 1, 6, 14

Common Pitfalls and Interview Tips

  • State the height convention explicitly to avoid off-by-one disagreements.

  • Do not assume O(log n) for every BST; mention the balance condition.

  • Clarify how duplicate keys are handled before implementing insertion.

  • State whether an operation mutates the tree; deletion normally does, while traversal does not.

  • Python integers do not overflow, but fixed-width languages require care when using keys or derived values outside their numeric range.

  • An ordinary tree traversal needs no visited set; one is needed only if the structure can contain cycles or shared references.

  • Common follow-up questions include validating a BST, finding the lowest common ancestor, computing tree diameter, and explaining how AVL or red-black trees restore balance.

16

How do insertion and deletion maintain Red-Black Tree properties?

Red-Black Tree rebalancing preserves binary-search-tree ordering while enforcing color and path constraints through rotations and recoloring. Insertions usually introduce a red-red violation, while deletions may create an “extra black” condition that also requires rebalancing.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Properties

A valid Red-Black Tree satisfies five rules:

  • Every node is either red or black.

  • The root is black.

  • Every None leaf is treated as a black sentinel node.

  • A red node cannot have a red child.

  • Every path from a node to its descendant None leaves contains the same number of black nodes.

These constraints guarantee that the tree height is O(log n), so ordinary lookup, insertion, and deletion remain efficient.

Insertion and Deletion

  • Insertion: The new node is initially red, because inserting a black node could immediately violate the equal-black-height rule. If its parent is red, the algorithm recolors nodes and performs left or right rotations until the red-red violation is removed.

  • Deletion: The standard approach replaces the deleted node with its inorder successor when necessary. Removing a red node normally requires no repair. Removing a black node can reduce the black height on one path, so the algorithm temporarily treats the replacement node as having an extra black unit and resolves it using sibling recoloring and rotations.

  • Rotations preserve the inorder sequence, so they do not change the tree’s sorted ordering.

For example, inserting 10, 20, and 30 proceeds as follows:

  1. 10 becomes the black root.

  2. 20 is inserted as a red right child.

  3. 30 creates a red-red violation between 20 and 30.

  4. Because the uncle is black (NIL) and the nodes form a straight right-right line, recoloring 20 black and 10 red, then a single left rotation at 10, makes 20 the black root and restores the Red-Black Tree properties.

Complexity

For a valid Red-Black Tree with n nodes:

Operation Best Average Worst Auxiliary Space
Search O(1) for a trivial tree O(log n) O(log n) O(1)
Insertion O(1) for a trivial tree O(log n) O(log n) O(1)
Deletion O(1) for a trivial tree O(log n) O(log n) O(1)

Each operation follows a root-to-leaf path of length O(log n). Repairs use at most O(log n) rotations and recolorings. The implementation is iterative, so the recursion stack is O(1); auxiliary space excludes the input, stored tree, and returned output.

Code Example

class TreeNode:
    """Node used by the Red-Black Tree."""

    def __init__(self, val: int, color: str = "red") -> None:
        self.val = val
        self.color = color
        self.left: TreeNode | None = None
        self.right: TreeNode | None = None
        self.parent: TreeNode | None = None


class RedBlackTree:
    """Red-Black Tree supporting insertion and deletion."""

    def __init__(self) -> None:
        self.nil = TreeNode(0, "black")
        self.nil.left = self.nil
        self.nil.right = self.nil
        self.nil.parent = self.nil
        self.root = self.nil

    def _rotate(self, node: TreeNode, direction: str) -> None:
        if direction == "left":
            pivot = node.right
            node.right = pivot.left
            if pivot.left is not self.nil:
                pivot.left.parent = node
        else:
            pivot = node.left
            node.left = pivot.right
            if pivot.right is not self.nil:
                pivot.right.parent = node

        pivot.parent = node.parent
        if node.parent is self.nil:
            self.root = pivot
        elif node is node.parent.left:
            node.parent.left = pivot
        else:
            node.parent.right = pivot

        if direction == "left":
            pivot.left = node
        else:
            pivot.right = node
        node.parent = pivot

    def _insert_fix(self, node: TreeNode) -> None:
        while node.parent.color == "red":
            parent = node.parent
            grandparent = parent.parent

            if parent is grandparent.left:
                uncle = grandparent.right
                if uncle.color == "red":
                    parent.color = uncle.color = "black"
                    grandparent.color = "red"
                    node = grandparent
                else:
                    if node is parent.right:
                        node = parent
                        self._rotate(node, "left")
                        parent = node.parent
                        grandparent = parent.parent
                    parent.color = "black"
                    grandparent.color = "red"
                    self._rotate(grandparent, "right")
            else:
                uncle = grandparent.left
                if uncle.color == "red":
                    parent.color = uncle.color = "black"
                    grandparent.color = "red"
                    node = grandparent
                else:
                    if node is parent.left:
                        node = parent
                        self._rotate(node, "right")
                        parent = node.parent
                        grandparent = parent.parent
                    parent.color = "black"
                    grandparent.color = "red"
                    self._rotate(grandparent, "left")

        self.root.color = "black"

    def insert(self, value: int) -> None:
        """Insert a value, placing duplicates in the right subtree."""
        node = TreeNode(value, "red")
        node.left = node.right = self.nil
        parent = self.nil
        current = self.root

        while current is not self.nil:
            parent = current
            current = current.left if value < current.val else current.right

        node.parent = parent
        if parent is self.nil:
            self.root = node
        elif value < parent.val:
            parent.left = node
        else:
            parent.right = node

        self._insert_fix(node)

    def _minimum(self, node: TreeNode) -> TreeNode:
        while node.left is not self.nil:
            node = node.left
        return node

    def _transplant(self, removed: TreeNode, replacement: TreeNode) -> None:
        parent = removed.parent
        if parent is self.nil:
            self.root = replacement
        elif removed is parent.left:
            parent.left = replacement
        else:
            parent.right = replacement
        replacement.parent = parent

    def _delete_fix(self, node: TreeNode) -> None:
        while node is not self.root and node.color == "black":
            parent = node.parent

            if node is parent.left:
                sibling = parent.right
                if sibling.color == "red":
                    sibling.color = "black"
                    parent.color = "red"
                    self._rotate(parent, "left")
                    sibling = parent.right

                if sibling.left.color == sibling.right.color == "black":
                    sibling.color = "red"
                    node = parent
                else:
                    if sibling.right.color == "black":
                        sibling.left.color = "black"
                        sibling.color = "red"
                        self._rotate(sibling, "right")
                        sibling = parent.right
                    sibling.color = parent.color
                    parent.color = "black"
                    sibling.right.color = "black"
                    self._rotate(parent, "left")
                    node = self.root
            else:
                sibling = parent.left
                if sibling.color == "red":
                    sibling.color = "black"
                    parent.color = "red"
                    self._rotate(parent, "right")
                    sibling = parent.left

                if sibling.left.color == sibling.right.color == "black":
                    sibling.color = "red"
                    node = parent
                else:
                    if sibling.left.color == "black":
                        sibling.right.color = "black"
                        sibling.color = "red"
                        self._rotate(sibling, "left")
                        sibling = parent.left
                    sibling.color = parent.color
                    parent.color = "black"
                    sibling.left.color = "black"
                    self._rotate(parent, "right")
                    node = self.root

        node.color = "black"

    def delete(self, value: int) -> None:
        """Delete the first matching value if it exists."""
        removed = self.root
        while removed is not self.nil and removed.val != value:
            removed = removed.left if value < removed.val else removed.right

        if removed is self.nil:
            return

        original_color = removed.color

        if removed.left is self.nil:
            replacement = removed.right
            self._transplant(removed, removed.right)
        elif removed.right is self.nil:
            replacement = removed.left
            self._transplant(removed, removed.left)
        else:
            successor = self._minimum(removed.right)
            original_color = successor.color
            replacement = successor.right

            if successor.parent is removed:
                replacement.parent = successor
            else:
                self._transplant(successor, successor.right)
                successor.right = removed.right
                successor.right.parent = successor

            self._transplant(removed, successor)
            successor.left = removed.left
            successor.left.parent = successor
            successor.color = removed.color

        # Removing a black node can create an extra-black condition.
        if original_color == "black":
            self._delete_fix(replacement)

    def inorder(self) -> list[int]:
        """Return values in sorted order."""
        result: list[int] = []
        stack: list[TreeNode] = []
        current = self.root

        while stack or current is not self.nil:
            while current is not self.nil:
                stack.append(current)
                current = current.left
            current = stack.pop()
            result.append(current.val)
            current = current.right

        return result


tree = RedBlackTree()
for value in [10, 20, 30, 40, 50]:
    tree.insert(value)

tree.delete(20)
print(tree.inorder())  # [10, 30, 40, 50]

Common Pitfalls

  • Forgetting to color the root black after an insertion fix.

  • Treating None leaves as red instead of black sentinels.

  • Moving a successor without updating its parent or child pointers.

  • Forgetting that deletion repair is needed when the physically removed node was black.

  • Using recursive deletion on a very large tree; an iterative implementation avoids Python’s recursion-depth limit.

  • Assuming a general binary tree’s O(n) worst case applies to a valid Red-Black Tree: its color constraints keep the height at O(log n).

17

What is the time complexity of inserting into a red-black tree?

Insertion into a red-black tree takes O(log n) time in the best, average, and worst cases. The tree’s height is bounded by O(log n), so locating the insertion position and restoring the red-black properties both require logarithmic time.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Complexity

Let n be the number of nodes already in the tree.

Case Time Reason
Best O(log n) The tree height is Θ(log n), so even the shortest root-to-leaf path requires logarithmic steps.
Average O(log n) Red-black trees maintain a logarithmic height regardless of insertion order.
Worst O(log n) Rebalancing never increases the height beyond O(log n).
  • Auxiliary space: O(1) for an iterative implementation.

  • Recursion stack: O(1), because insertion and rebalancing can be done iteratively.

  • Total tree storage: O(n), including the newly inserted node.

  • Input mutation: The existing tree is modified in place.

Why It Stays Logarithmic

Insertion has two phases:

  1. Locate the position: Follow binary-search-tree comparisons downward from the root. A red-black tree has height O(log n), so this takes O(log n) time.

  2. Restore invariants: Insert the node as red, then recolor nodes and rotate where necessary. Fix-up requires O(log n) recoloring operations and at most a constant number of rotations.

Rotations and recoloring are individually O(1), but the number of recolorings can be proportional to the tree height.

Walkthrough

Inserting 10, 20, and 30 produces a right-right violation:

  1. 10 becomes the black root.

  2. 20 is inserted as its red right child.

  3. 30 is inserted as the red right child of 20.

  4. A left rotation around 10, followed by recoloring, makes 20 the black root with red children 10 and 30.

The inorder sequence remains [10, 20, 30].

Common Pitfalls

  • Do not claim O(n): That is the worst case for an ordinary unbalanced binary search tree.

  • Do not count rotations as O(log n) individually: Each rotation is O(1); the total number of rotations during insertion is constant.

  • Preserve root blackness: The root must always be black after insertion completes.

  • Handle duplicates explicitly: Define a policy, such as rejecting duplicate values or placing equal keys consistently on one side.

  • Common follow-up: Interviewers may ask for the difference between red-black-tree insertion and deletion, or why deletions can require more extensive rebalancing.

18

How does tree balancing improves search performance in a binary tree?

Tree balancing keeps a binary search tree’s height close to logarithmic by preventing long chains of nodes. Shorter paths mean fewer key comparisons, so searching becomes O(log n) instead of potentially O(n) in a skewed tree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Balancing Works

A binary tree allows each node to have at most two children, but it does not impose an ordering rule. A binary search tree (BST) stores keys so that all keys in a node’s left subtree are smaller and all keys in its right subtree are larger.

Self-balancing structures such as AVL trees, red-black trees, and treaps preserve the BST ordering while adjusting the tree’s shape. They commonly use rotations, which rearrange a small group of parent and child nodes without changing their key order.

  • AVL trees maintain strict height balance and usually provide faster lookups.

  • Red-black trees allow slightly looser balance and are well suited for frequently updated structures.

  • Treaps use randomized priorities to maintain expected balance.

Balancing a binary tree without preserving the BST invariant does not improve ordered search; the search keys must still be organized correctly.

Search Performance

In a BST, each comparison determines which single subtree can contain the target. Therefore, search time depends primarily on the tree’s height.

Tree shape Height Search time Extra space
Balanced BST O(log n) O(log n) O(1) iterative, O(log n) recursive
Randomly ordered BST O(log n) expected O(log n) average O(1) iterative, O(log n) recursive
Skewed BST O(n) O(n) worst case O(1) iterative, O(n) recursive

For a balanced tree:

  • Best case: O(1), when the target is the root.

  • Average case: O(log n), because a typical search follows part of one root-to-leaf path.

  • Worst case: O(log n), because every valid path remains logarithmically short.

  • Space: O(1) for an iterative search or O(h) for a recursive search, including the recursion stack. The input tree itself is not counted as additional space.

For an unbalanced BST, the worst case is O(n), while the best case is still O(1).

Step-by-Step Example

Consider searching for key 7 in seven keys:

Tree shape Search path Comparisons
Skewed right: 1 → 2 → 3 → 4 → 5 → 6 → 7 1 → 2 → 3 → 4 → 5 → 6 → 7 7
Balanced: root 4, with children 2 and 6 4 → 6 → 7 3

The balanced tree has height 2, counting edges, while the skewed tree has height 6. The improvement comes from reducing the number of nodes inspected along the search path.

Related Tree Properties

These terms describe different properties and should not be used interchangeably:

  • Binary tree: Each node has at most two children.

  • Binary search tree: A binary tree with the BST key-ordering invariant.

  • Complete tree: Every level is full except possibly the last, which is filled from left to right.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has two children, and all leaves are at the same depth.

  • Balanced tree: The heights of the left and right subtrees differ by no more than a defined constant.

A balanced BST is not necessarily complete, full, or perfect, although a perfect tree is balanced.

Common Pitfalls

  • Balancing does not replace ordering: Without the BST invariant, lookup cannot consistently select one subtree.

  • Height conventions differ: This answer counts edges, so a one-node tree has height 0 and an empty tree has height -1.

  • Do not ignore recursion depth: A skewed tree with more than roughly 1,000 nodes can exceed Python’s default recursion limit.

  • Rebalancing adds update cost: Insertion and deletion in an AVL tree remain O(log n), but rotations and balance checks make them slightly more expensive than in an ordinary BST.

  • Interview follow-ups: Interviewers commonly ask about AVL versus red-black trees, rotations, height versus depth, insertion and deletion complexity, and how to find the kth smallest key.

19

What are immutable binary trees in functional programming?

An immutable binary tree is a tree whose nodes and references cannot be changed after construction. Updates therefore produce a new tree while safely sharing unchanged subtrees with previous versions, which makes immutable trees particularly valuable in functional programming.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Immutability is a property of how a tree is managed, not a structural shape. It is independent of the tree’s classification:

Term Exact meaning
Binary tree Every node has at most two children, conventionally named left and right.
Binary search tree (BST) A binary tree with the ordering invariant that values in the left subtree are smaller and values in the right subtree are larger, according to the tree’s comparison rule.
Complete tree Every level is full except possibly the last, which is filled from left to right.
Full tree Every node has either zero or two children.
Perfect tree Every internal node has two children, and all leaves have the same depth.
Balanced tree The heights of each node’s subtrees differ by at most one at every node.

In a strictly functional setting, immutability is usually combined with persistence: modifying a tree returns a new root, but the old root and all older versions remain valid.

For example, if a root has left and right subtrees, changing the root’s value creates a new root that references the same two subtrees. Only the path from the changed node to the root must be rebuilt.

Functional Programming Implications

  • Referential transparency: A tree version always represents the same contents when given the same inputs. Code can pass it between functions without unexpected mutation.

  • Structural sharing: Unchanged subtrees are reused rather than copied, reducing the cost of versioned updates.

  • Safe concurrency: Functions cannot race by modifying shared tree nodes. Multiple threads can read and update separate versions without corrupting one another.

  • Easy undo and history: Keeping the previous root provides a previous version. A sequence of updates can be represented as a chain of persistent roots.

  • Composability: Trees can be combined using pure functions, such as merging, filtering, mapping, or folding, without requiring defensive copies.

  • Predictable ownership: No function can unexpectedly change a caller’s tree. Changes must be returned explicitly.

This differs from a conventional mutable tree, where insertion or deletion often rewires existing nodes. In a persistent tree, the original version must remain unchanged, so affected nodes are newly allocated.

Complexity

Let n be the number of nodes, h the tree height measured in edges, and w the maximum number of nodes at one level. Auxiliary space excludes the original input tree but includes recursion stacks.

Operation Time Auxiliary space Reason
Search O(h) O(1) iterative or O(h) recursive One root-to-leaf path is examined; the recursive call stack uses O(h).
Persistent update O(h) O(h) A new node is allocated for each node on the affected path.
DFS traversal O(n) O(h) Every node is visited once; the stack holds at most O(h) nodes.
BFS traversal O(n) O(w) The queue can contain nodes from multiple levels.
Full copy O(n) O(n) Every node must be recreated without structural sharing.

For a balanced tree, h is O(log n), so search and persistent updates are O(log n). For a skewed tree, h is O(n), making both O(n). Persistence does not automatically guarantee logarithmic updates; the tree must also maintain an appropriate balance invariant.

Common Pitfalls

  • Assuming updates are O(1): Creating a new root is constant-time, but producing a correct new tree may require rebuilding an entire root-to-leaf path.

  • Mutating shared nodes: Replacing an existing child changes every version that references that node. Create new nodes instead.

  • Confusing immutability with shape: An immutable binary tree is not necessarily a BST, complete, full, perfect, or balanced.

  • Retaining excessive history: Older roots can keep obsolete subtrees alive through structural sharing. Garbage collection reclaims them only when no version references them.

  • Ignoring equality semantics: Two trees can contain equal values but have different node identities. Interviewers may ask how structural equality should be defined.

  • Oversimplifying concurrency: Immutable structures remove data races on tree nodes, but side effects such as logging or external I/O still require synchronization where necessary.

20

What distinguishes a binary tree from a binary search tree?

A binary tree is a tree in which each node has at most two children, conventionally named left and right. A binary search tree (BST) is a specialized binary tree that also maintains an ordering property, allowing efficient searching, insertion, and deletion.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Property Binary Tree Binary Search Tree
Child limit At most two children per node At most two children per node
Ordering No ordering requirement Every key in the left subtree is smaller than the node; every key in the right subtree is larger
Purpose Representing hierarchical structures Efficient searching and ordered operations
Search complexity Usually O(n) because values are unordered O(h), where h is the tree height
Inorder traversal Produces no guaranteed order Produces keys in sorted order when keys are unique

A node with one child is valid in both structures. The binary tree rule does not require a node to have exactly two children.

Example

Consider this tree:

8
       / \
      3   10
     / \    \
    1   6    14

It is both a binary tree and a BST because:

  • The root is 8.

  • Every node in the left subtree is less than 8.

  • Every node in the right subtree is greater than 8.

  • The same ordering property holds within each subtree.

If the root’s left child were changed from 3 to 9, the tree would remain a binary tree but would no longer be a valid BST.

For the original tree, the traversal orders are:

  • Preorder: 8, 3, 1, 6, 10, 14

  • Inorder: 1, 3, 6, 8, 10, 14

  • Postorder: 1, 6, 3, 14, 10, 8

  • Level order: 8, 3, 10, 1, 6, 14

Related Tree Classifications

These properties are separate from the BST ordering rule:

Classification Exact definition
Full binary tree Every node has either zero or two children
Complete binary tree Every level except possibly the last is completely filled, and the last level is filled from left to right
Perfect binary tree Every internal node has exactly two children, and all leaves have the same depth
Balanced binary tree For every node, the heights of its left and right subtrees differ by at most one
BST Every left-subtree key is smaller and every right-subtree key is greater than the node’s key

A binary tree does not have to be full, complete, perfect, or balanced. Similarly, a BST can be balanced or highly skewed.

Complexity

For a tree containing n nodes and having height h:

Operation Time complexity Reason
Traversal O(n) best, average, and worst Every node is visited once
Search in an arbitrary binary tree O(1) best, O(n) average and worst Without ordering, most values may require inspecting every node
Search in a BST O(h) worst The search follows one root-to-leaf path
Search in a balanced BST O(1) best, O(log n) average and worst Balanced height is O(log n)
Search in a skewed BST O(1) best, O(n) worst The tree resembles a linked list

For n nodes, h is O(log n) when the tree is balanced and O(n) when it is completely skewed.

Auxiliary traversal space depends on the algorithm:

  • DFS: O(h), including the recursion stack or explicit stack.

  • BFS: O(w), where w is the maximum number of nodes at one level.

These space bounds exclude the input tree itself.

Common Pitfalls

  • Confusing height conventions: This answer counts height in edges, so an empty tree has height -1 and a single-node tree has height 0.

  • Assuming every binary tree is sorted: Only a correctly constructed BST guarantees sorted inorder traversal.

  • Ignoring duplicates: A strict BST rejects duplicate keys. Other implementations place equal keys consistently on one side, producing a nondecreasing inorder sequence.

  • Assuming every BST is balanced: A valid BST can become O(n) deep after inserting already sorted values.

  • Mutating the input unnecessarily: Read-only operations should preserve the tree unless modification is explicitly required.

  • Forgetting traversal order: Preorder visits root-left-right, inorder visits left-root-right, postorder visits left-right-root, and level order visits nodes by depth.

  • Common interview follow-up: Interviewers often ask for an iterative traversal, validation of the BST property, or an explanation of how rotations preserve BST ordering while changing its height.

21

How do binary heaps and red-black trees differ?

A binary heap is designed to efficiently access the smallest or largest element, while a red-black tree is a balanced binary search tree designed to maintain sorted order. Both provide logarithmic-time updates, but they optimize different operations and use different balancing mechanisms.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Differences

Property Binary heap Red-black tree
Primary purpose Priority queue, heap sort, scheduling Ordered dictionary, map, set
Tree shape Complete binary tree Balanced binary search tree
Ordering Parent is smaller or larger than its children, depending on min-heap or max-heap All keys in the left subtree are no greater than the node, and all keys in the right subtree are no smaller
Global ordering Not guaranteed In-order traversal produces sorted keys
Duplicate keys Supported naturally Supported with an explicit duplicate-handling policy
Typical storage Contiguous array Linked nodes containing key, parent, children, and color
Balancing method Completeness of the tree shape Recoloring and rotations enforce red-black constraints

A binary heap does not have to be a binary search tree. For example, a min-heap only guarantees that each parent is no greater than its children; it does not guarantee that an in-order traversal is sorted.

A red-black tree does not normally satisfy the heap property. Its left subtree contains smaller keys and its right subtree contains larger keys, so it preserves sorted order across the entire tree.

Structure and Invariants

A standard binary heap is a complete binary tree: every level is full except possibly the last, which is filled from left to right. This gives it a height of ⌊log₂(n)⌋ edges, where n is the number of elements.

A red-black tree assigns each node a red or black color and maintains these properties:

  • Every node has one of the two colors.

  • The root is black.

  • Leaves represented by NIL children are black.

  • A red node cannot have a red child.

  • Every path from a node to its descendant NIL leaves contains the same number of black nodes.

These rules keep the longest root-to-leaf path at most approximately twice the shortest one. Consequently, the red-black tree remains height-balanced and prevents the O(n) height that an ordinary unbalanced binary search tree can reach.

Operation Complexity

For n elements:

Operation Binary heap Red-black tree Reason
Insert O(log n) worst case O(log n) worst case Heap bubbles up; tree uses rotations and recoloring
Remove root O(log n) worst case O(log n) worst case Both restore their structure along one path
Remove arbitrary element O(n) worst case O(log n) worst case A heap must first locate the element; a tree uses its ordering
Search for a key O(n) worst case O(log n) worst case Heap keys are only partially ordered; tree keys are globally searchable
Peek at root O(1) O(1) Direct access to the root
Find minimum or maximum O(1) O(log n) typically Heap stores the extreme value at the root; tree follows child links
Build from unsorted input O(n) using heap construction O(n log n) using repeated insertions Bottom-up heapification processes each node efficiently
Traverse all elements O(n) O(n) Every node must be visited

These bounds have the same asymptotic complexity in the average case for standard deterministic implementations. A heap’s lack of global ordering means that even an average-case arbitrary search can require examining every element.

Space Accounting

  • Stored structure: Both use O(n) space for their nodes or array elements.

  • Heap updates: An iterative heap operation typically uses O(1) auxiliary space. A recursive implementation may use O(log n) recursion-stack space.

  • Red-black updates: A recursive implementation typically uses O(log n) auxiliary space for the recursion stack. An iterative implementation can use O(1) auxiliary space when it maintains parent links.

  • Traversal space: DFS uses O(h) stack space, while BFS uses O(w) queue space, where w is the maximum level width. These bounds exclude the stored tree itself.

  • Height is measured in edges here. For both a complete heap and a balanced red-black tree, h is O(log n).

Small Example

Consider inserting 5, 3, 8, and 1 into a min-heap and a red-black tree:

  1. After inserting 5, the heap contains [5]; the tree has a black root with key 5.

  2. After inserting 3, the heap becomes [3, 5]; the tree places 3 as a red left child of 5.

  3. After inserting 8, the heap becomes [3, 5, 8]; the tree places 8 as a red right child of 5.

  4. Inserting 1 into the heap: append to get [3, 5, 8, 1], then bubble up past 5 and 3 to become [1, 3, 8, 5].

  5. Inserting 1 into the red-black tree: it becomes a red left child of 3. This creates a red-red violation (3 is red, 1 is red). The tree rebalances by recoloring 3 and 8 to black and 5 to red, then setting the root 5 back to black. The final tree has root 5 (black), children 3 (black) and 8 (black), and 1 as a red left child of 3. Its in-order traversal is 1, 3, 5, 8.

The heap’s array is only partially ordered, while the red-black tree explicitly preserves sorted order.

Common Pitfalls and Interview Tips

  • Do not call a binary heap a heap-ordered binary search tree; it generally is not globally sorted.

  • Do not confuse tree height with depth: depth is the distance from the root to a node.

  • Do not assume finding an arbitrary value in a heap is O(log n); that bound applies to root access and structural updates.

  • Red-black trees guarantee O(log n) height, but ordinary unbalanced binary search trees can degrade to O(n) operations.

  • Interviewers often ask which structure to choose for a priority queue, an ordered map, duplicate handling, or a large number of insertions and deletions.

22

How do Tries differ from Binary Search Tries?

A Trie is a prefix tree whose edges represent characters, while a Binary Search Trie—used here for a binary search tree (BST) storing complete strings—orders keys lexicographically. Tries are strongest for prefix operations; balanced BSTs are general-purpose ordered-key structures.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

  • Trie: Each node represents a path prefix and can have one outgoing edge per possible character. Searching "car" follows c → a → r.

  • Binary Search Trie / BST: Each node stores a complete string. Its left subtree contains lexicographically smaller strings, and its right subtree contains larger strings.

  • Prefix queries: A Trie locates the prefix subtree directly. A BST finds a lower bound and then scans a bounded contiguous range.

  • Ordering: A Trie primarily supports prefix traversal. A BST supports sorted iteration, range queries, predecessors, and successors.

  • Key representation: A Trie distributes characters across nodes. A BST stores each complete key in one node, although child references consume additional memory.

“Binary Search Trie” is not standardized; this comparison uses the BST interpretation.

A BST is binary because each node has at most two children, but it is not automatically complete, full, perfect, or balanced:

  • Complete: Every level is filled except possibly the last, which is filled from left to right.

  • Full: Every node has either zero or two children.

  • Perfect: Every internal node has two children, and all leaves have the same depth.

  • Balanced: Under the AVL-style definition, the heights of the left and right subtrees differ by at most one at every node.

Complexity Comparison

Let:

  • n = number of stored keys

  • L = length of the searched key

  • p = length of the searched prefix

  • S = total number of characters across all stored keys

The table assumes successful exact lookups and measures the cost of locating prefix results without materializing them.

Structure and operation Best Average Worst
Trie exact lookup O(L) O(L) O(L)
Balanced BST exact lookup O(L) O(L log n) O(L log n)
Unbalanced BST exact lookup O(L) O(L log n) O(nL)
Balanced BST insertion O(L log n) O(L log n) O(L log n)
Unbalanced BST insertion O(L) O(L log n) O(nL)
Trie prefix lookup O(p) O(p) O(p)
Balanced BST prefix lookup O(p) O(p log n) O(p log n)
Unbalanced BST prefix lookup O(p) O(p log n) O(np)
  • Trie lookup: O(L) because each character is followed once along one path.

  • BST lookup: A balanced tree has O(log n) levels, but comparing complete strings can cost O(L); comparisons against a prefix can cost O(p).

  • Unbalanced BST: Its height can reach n, making lookup and insertion O(nL).

  • Average-case assumption: The average unbalanced-BST bounds assume random insertion order and independently selected lookup keys.

  • Prefix output: Add the cost of inspecting the matching range or Trie subtree and returning the matching keys.

Space and Structural Trade-offs

  • Trie storage: O(S) for nodes and character links when the alphabet size is fixed. This counts the constructed Trie and excludes the original input collection.

  • BST storage: O(n) for node metadata, plus O(S) if complete strings are copied into nodes. If nodes reference existing strings, the additional structure uses O(n) space.

  • Recursion stack: Recursive exact-key Trie operations use O(L) stack space; recursive prefix enumeration uses O(D), where D is the maximum Trie depth. Recursive BST operations use O(h) stack space.

  • Height convention: Height counts edges, so an empty tree has height -1 and a root-only tree has height 0. For a BST, h is O(log n) when balanced and O(n) when skewed.

  • Iterative operations: Exact lookups can follow one path using O(1) auxiliary space. General DFS traversals instead use stack space proportional to tree or Trie depth.

  • Memory overhead: Long strings can make a Trie node-heavy because it creates one node per distinct prefix. Shared prefixes reduce the number of nodes relative to storing every complete key independently and enable efficient prefix navigation.

  • General-purpose use: Prefer a self-balancing BST for an ordered map. Prefer a Trie for autocomplete, dictionary prefix matching, or many prefix-oriented queries.

Small Example

For the keys "car", "card", "cat", and "dog":

  1. In a Trie, the shared path c → a → r represents the prefix "car".

  2. The node at "car" has children for "d" and "t", separating "card" and "cat".

  3. Looking up "car" examines three characters.

  4. The "dog" key begins at a different root child.

  5. A valid BST’s inorder traversal is "car", "card", "cat", "dog".

  6. Finding all "car" keys in the Trie follows one prefix path; in a BST, it requires a lower-bound search followed by range scanning.

Common Pitfalls

  • Empty input: An empty Trie still has a root; an empty string requires an explicit policy. A BST can store an empty string as an ordinary key.

  • Single key: A root-only BST has height 0, but a Trie storing one length-L key has depth L.

  • Duplicates: A Trie usually needs a count or terminal flag. A BST needs a defined policy, such as replacing the value or maintaining a count.

  • Already sorted input: Inserting sorted keys into an ordinary BST can create a skewed tree; use an AVL or red-black tree if balance is required.

  • Negative numeric keys: If the BST stores numbers rather than strings, its comparator must handle negative values correctly.

  • Terminology: Confirm whether “Binary Search Trie” means a string-keyed BST or a binary Trie over {0, 1}. A binary Trie follows bit paths and also has linear path-operation costs.

  • Interview follow-ups: Common questions ask about prefix enumeration, duplicate handling, memory consumption, balancing, and sorted iteration.

23

Red-Black Tree vs AVL Tree differences

Red-black trees (RBTs) and AVL trees are self-balancing binary search trees with O(log n) worst-case height. AVL trees maintain stricter balance, so their paths are generally shorter and lookups can be faster, while red-black trees usually require fewer rotations on updates and are often preferred for write-heavy workloads.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Invariants

  • AVL tree: For every node, the heights of its left and right subtrees differ by at most 1. The balance factor is therefore −1, 0, or 1, depending on the height convention. Insertions and deletions restore this invariant using single or double rotations.

  • Red-black tree: A common formulation gives every node a red or black color and maintains these properties:

  • The root is black.

  • External NIL leaves are black.

  • A red node cannot have a red child.

  • Every path from a node to a descendant NIL leaf contains the same number of black nodes, called the black-height.

  • These invariants make both trees valid binary search trees while preventing linear height.

  • Red-black trees have a looser balance: the longest root-to-leaf path is at most twice the shortest. AVL trees have a tighter balance and generally shorter paths.

Height and Complexity

Let n be the number of nodes and h the tree height measured in edges.

Tree type Standard height upper bound Worst-case height
AVL h ≤ 1.4405 log₂(n + 2) - 0.3277 O(log n)
Red-black h ≤ 2 log₂(n + 1) O(log n)

These formulas are upper bounds, not exact maximum heights for every n.

Operation Best case Average case Worst case Reason
Search O(1) O(log n) O(log n) A search follows one root-to-leaf path of length O(h); finding the root is the best case.
Insertion O(1) O(log n) O(log n) The tree is initially empty in the best case; otherwise, locating the position and repairing the path costs O(h).
Deletion O(1) O(log n) O(log n) Removing a node and restoring the invariant requires traversing and possibly repairing an O(h) path.

Counting the stored tree itself, total space is O(n). Auxiliary space is O(h) for a recursive implementation because the recursion stack is included; an iterative search can use O(1) auxiliary space, while an iterative update commonly needs an O(h) path stack. In these self-balancing trees, h is O(log n); in a general skewed binary tree, h can be O(n).

Insertion and Deletion

  • AVL insertion: Requires at most 2 rotations.

  • AVL deletion: Can require O(log n) rotations in the worst case because several ancestors may become unbalanced.

  • Red-black insertion: Requires at most 2 rotations, although recoloring may propagate upward.

  • Red-black deletion: Requires at most 3 rotations, but may also recolor ancestors along the search path.

  • Each rotation takes O(1) time. Repairing the path can affect O(h) ancestors, so both insertion and deletion remain O(log n) overall.

  • Red-black trees generally perform fewer rotations; AVL trees generally perform less recoloring and have more straightforward update logic.

Memory Overhead

  • AVL tree: Stores either a balance factor or an integer subtree height per node. A balance factor has three possible values and can theoretically be encoded in 2 bits, but implementations often allocate an integer field.

  • Red-black tree: Stores one logical color bit per node, although implementations may allocate a whole byte or encode color in another field.

  • Both use O(n) total storage for the tree. Red-black trees have slightly less theoretical metadata overhead, but actual memory usage depends on the implementation and allocator.

Choosing a Tree

  • Use AVL when lookups dominate: Read-mostly ordered indexes can benefit from AVL trees’ shorter average search paths, especially when updates are rare.

  • Use red-black when updates are frequent: Fewer rotations can reduce update latency. Examples include Java’s TreeMap, the Linux kernel’s rb_tree, and the red-black implementations commonly used by C++ standard libraries for std::map and std::set.

  • Do not assume a C++ implementation is fixed by the standard: The C++ standard specifies the behavior of std::map and std::set, but not their internal balancing algorithm.

  • Use B-tree-like indexes for disk storage: Their fan-out matches storage pages and reduces I/O. LSM-tree architectures are another option for write-heavy persistent workloads, rather than a direct replacement for every in-memory tree.

Common Pitfalls

  • Mixing height conventions: Define whether an empty tree has height −1 or 0, and apply that convention consistently to balance factors.

  • Ignoring NIL leaves: Red-black implementations often use a shared black sentinel. State whether black-height counts the starting node and sentinel leaves.

  • Stopping AVL deletion too early: Continue updating ancestors and rotating until the original root is reached or the tree is known to be balanced.

  • Assuming red-black deletion is simpler: Its fixup procedure is generally more involved than AVL deletion, despite requiring at most 3 rotations.

  • Common follow-up: Add a subtree-size field to support order-statistic operations. Rank and selection queries take O(h) = O(log n) time with either tree; AVL trees may have a small constant advantage from shorter paths, but both have the same asymptotic complexity.

24

When are standard BSTs preferred over AVL trees?

An ordinary binary search tree (BST) is often preferred when simplicity and low per-node overhead matter more than guaranteed logarithmic performance. This is common for read-heavy applications, prototypes, or workloads where insertion order is unlikely to create a severely skewed tree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Difference

A standard BST stores keys so that:

  • The left subtree contains smaller keys.

  • The right subtree contains larger keys.

  • Each node has at most two children.

An AVL tree is also a binary search tree, but it maintains a balance condition: for every node, the heights of its left and right subtrees differ by at most one.

Therefore, an ordinary BST may become severely unbalanced, while an AVL tree always maintains a height of (O(log n)) for (n) nodes.

Complexity Comparison

The average BST results assume keys are inserted in an order that produces a reasonably balanced tree. Sorted insertion is a common worst-case scenario.

Operation Standard BST Best Standard BST Average Standard BST Worst AVL Best AVL Average AVL Worst
Search (O(1)) (O(log n)) (O(n)) (O(1)) (O(log n)) (O(log n))
Insertion (O(1)) on an empty tree (O(log n)) (O(n)) (O(1)) on an empty tree (O(log n)) (O(log n))
Deletion (O(1)) when deleting the root (O(log n)) (O(n)) (O(log n)) (O(log n)) (O(log n))
  • Time reason: Traversing a balanced tree follows one root-to-leaf path of (O(log n)). A skewed ordinary BST can require visiting all (n) nodes.

  • Auxiliary space: (O(1)) for iterative operations or (O(h)) for recursive operations, including the recursion stack.

  • Input space: The existing tree occupies (O(n)) and is not included in auxiliary space.

  • Height: In an ordinary BST, (h) can be (O(n)); in an AVL tree, (h) is always (O(log n)).

  • Per-node storage: AVL nodes require additional balance metadata, while ordinary BST nodes generally require only a key and child references. The total storage remains (O(n)) for both.

When a Standard BST Is Preferred

  • Read-heavy workloads: Search cost is usually acceptable when the tree remains reasonably balanced.

  • Simple implementations: A standard BST avoids rotations and balance-factor maintenance.

  • Lower memory overhead: No height or balance information must be stored for each node.

  • Prototypes and educational examples: The basic BST operations are easier to implement and reason about.

  • Stable, controlled insertion order: If the application can guarantee balanced-enough input, the stronger AVL guarantee may provide little practical benefit.

  • Batch construction: A tree that is built once and then queried extensively may not justify balancing overhead during construction.

When an AVL Tree Is Better

Choose an AVL tree when:

  • Search, insertion, and deletion must consistently remain (O(log n)).

  • Input order is unknown or may be sorted, reverse-sorted, or otherwise adversarial.

  • Predictable latency is more important than minimizing per-node memory.

  • The data structure is maintained continuously through many updates.

Other self-balancing trees may also be appropriate. For example, red-black trees generally perform fewer rotations and are often favored in ordered associative containers, whereas AVL trees favor more rigid balance and faster lookups.

Common Pitfalls

  • Confusing BST with balanced BST: A binary search tree is defined by key ordering, not by balance.

  • Assuming average-case balance always holds: Inserting sorted keys into an ordinary BST produces a chain with (O(n)) height and worst-case operations.

  • Ignoring duplicate keys: A duplicate-handling policy must be defined consistently; rejecting or counting duplicates preserves the basic BST invariant.

  • Choosing by average behavior only: If performance guarantees matter, the AVL tree is safer because ordinary BST operations are only (O(log n)) on average.

  • Ignoring recursion depth: Recursive operations on a skewed ordinary BST can reach depth (O(n)). An iterative implementation avoids Python’s default recursion-limit concern.

25

Splay Tree vs Red-Black Tree performance comparison

Splay trees and Red-Black trees are both self-adjusting binary search trees, but they offer different performance guarantees: splay trees provide amortized O(log n) bounds with excellent locality of reference, while Red-Black trees guarantee O(log n) worst-case time for every operation.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How They Work

  • Splay Tree: After every access (search, insert, delete), the accessed node is moved to the root through a sequence of rotations called splaying (zig, zig-zig, zig-zag). No explicit balance information is stored.

  • Red-Black Tree: Maintains balance by coloring nodes red or black and enforcing five invariants (root is black, leaves are black, red nodes have black children, every path has same black-height). Rebalancing uses rotations and recoloring after inserts/deletes.

Time Complexity Comparison

Operation Splay Tree (Amortized) Splay Tree (Worst Case) Red-Black Tree (Worst Case)
Search O(log n) O(n) O(log n)
Insert O(log n) O(n) O(log n)
Delete O(log n) O(n) O(log n)
Min/Max O(log n) O(n) O(log n)
Successor O(log n) O(n) O(log n)

Reason: Splay tree bounds are amortized over a sequence of operations (potential method). A single operation can take O(n) when the tree becomes a linear chain. Red-Black tree height is at most 2 log₂(n+1), giving strict worst-case guarantees.

Space Complexity

Aspect Splay Tree Red-Black Tree
Node overhead 2 pointers (left, right) 2 pointers + 1 color bit
Auxiliary space (recursion/stack) O(h) = O(n) worst, O(log n) amortized O(log n) worst
Parent pointers Often omitted (top-down splay) Usually required for deletion

Both are O(n) total space for n nodes. Red-Black trees need one extra bit per node; splay trees often avoid parent pointers by using top-down splaying.

When to Use Which

  • Choose Splay Tree when:

  • Access pattern has strong locality of reference (recently accessed items likely to be accessed again)

  • Simplicity of implementation is valued (no color bits, fewer rotation cases)

  • Amortized bounds are acceptable and worst-case latency spikes are tolerable

  • Used in caches, memory allocators, or rope data structures

  • Choose Red-Black Tree when:

  • Real-time or worst-case guarantees are required

  • Consistent latency matters (databases, language standard libraries)

  • Concurrent access is needed (easier to lock with predictable height)

  • Used in std::map (C++), TreeMap (Java), dict (Python 3.7+ uses hash table, but RB-tree is classic)

Practical Trade-offs

  • Constant factors: Red-Black trees have higher constant factors due to color checks and more rotation cases. Splay trees do more rotations per access but simpler logic.

  • Cache behavior: Splay trees move hot nodes to root, improving cache locality for skewed workloads. Red-Black trees keep tree shallow but don’t adapt to access frequency.

  • Persistence/Functional use: Red-Black trees are easier to make persistent (path copying). Splay trees mutate heavily on every read.

  • Parallelism: Red-Black trees’ bounded height makes fine-grained locking practical. Splay trees’ restructuring on reads complicates concurrent access.

Common Pitfalls

  • Assuming splay tree worst case is rare: A sequence of ascending inserts creates a linked list; subsequent search of the smallest element takes O(n) every time until the tree is rebalanced by other accesses.

  • Forgetting amortized ≠ worst-case: In latency-sensitive systems (trading, gaming), a single O(n) splay operation can cause a frame drop or timeout.

  • Omitting parent pointers in Red-Black delete: Deletion fix-up requires walking up the tree; without parent pointers you need a stack or recursion (O(log n) space).

  • Treating splay trees as thread-safe: Every read mutates the tree. External synchronization is mandatory for concurrent access.

  • Interview follow-up: “How would you implement a splay tree without parent pointers?” (Top-down splaying with a dummy root) or “Why does Java’s TreeMap use Red-Black and not AVL?” (Fewer rotations on insert/delete, faster in practice).

26

What distinguishes B+ trees from B-trees, including when each is preferred?

A B+ tree is a balanced multiway search tree that stores all records in linked leaves, while a B-tree can store records in both internal and leaf nodes. B+ trees are especially effective for database indexes and range queries because leaf records are packed together and can be traversed sequentially.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Structural Differences

Property B-tree B+ tree
Internal nodes Store keys and record payloads or payload references Store separator keys and child pointers, but not full records
Leaf nodes Store keys and record payloads Store all user-visible keys and record payloads
Search termination A search can stop at an internal node A search continues to a leaf node
Leaf connections Leaves are not normally linked Leaves are linked, usually in ascending key order
Key placement Each index entry is stored once, either internally or in a leaf User-visible entries remain in leaves; separator copies may also appear internally
Common strength Efficient point lookups Efficient point lookups, range scans, and ordered traversal

Duplicate user values are an index-semantics choice rather than a structural distinction: either structure can represent them, depending on the index definition. A separator key in a B+ tree indicates a boundary between child subtrees. Depending on the implementation, it may be an exact copy of a key in a leaf or represent the largest key in a child subtree.

How Searches and Range Scans Work

In a B-tree, the algorithm compares the target with keys in the current node:

  1. It stops if the target is found.

  2. Otherwise, it follows the appropriate child pointer.

  3. It may find the record before reaching a leaf.

In a B+ tree, internal nodes only determine the correct route:

  1. The algorithm uses separator keys to select a child.

  2. It repeats until reaching the first matching leaf.

  3. It then scans the matching leaf and subsequent linked leaves until the range ends.

For example, if the leaves contain [10, 20], [30, 40], and [50, 60], a query for values from 25 through 50 first locates the leaf containing 30. It then follows the leaf links and returns 30, 40, and 50.

Complexity

Let:

  • n be the number of indexed records.

  • h be the tree height.

  • F be the fixed fanout—the maximum number of children per node for a given node or page size.

For a properly balanced B-tree or B+ tree:

Operation Best Average Worst Reason
B-tree point lookup O(1) O(log_F n) O(log_F n) The search may find the target at the root; otherwise it selects one child per level
B+ tree point lookup O(log_F n) O(log_F n) O(log_F n) The search descends through internal nodes and then examines a leaf
B-tree ordered range query O(h + k) O(h + k) O(h + k) With subtree pruning, it visits relevant nodes and returns k records
B+ tree ordered range query O(h + k) O(h + k) O(h + k) It descends once and scans k records through linked leaves

Here, k is the number of records returned. The O(1) best case for B-tree lookup occurs only when the target is stored in the root; a B+ tree has the same special case only when its root is a leaf.

Because fanout is fixed, selecting one child and searching within a node take constant time asymptotically, and log_F n is conventionally written as O(log n). If fanout is allowed to vary, binary search within each node can add O(log F) work per level, yielding O(log n) comparisons overall. A naive B-tree implementation that restarts a separate search for each range key can instead take O(kh).

  • Total storage space: O(n) for either structure, counting stored records, keys, and pointers.

  • Auxiliary lookup space: O(h) for recursion or O(1) with an iterative search.

  • Range-result space: O(k) if results are materialized; a streaming linked-leaf scan can use O(1) output workspace.

  • These auxiliary figures exclude caller-owned input and returned output unless explicitly stated.

When B+ Trees Are Preferred

B+ trees are commonly preferred for:

  • Database indexes: Point queries are fast, while range predicates such as WHERE date BETWEEN ... can scan leaves sequentially.

  • File systems: Large fanout reduces tree height, minimizing disk seeks.

  • Ordered traversal: Linked leaves make iterating through all records efficient.

  • Disk-oriented workloads: Records are concentrated in leaves, improving page locality and cache utilization.

  • Covering indexes: When every selected column is available in the leaf entries, the database may answer a query without loading full table rows.

A B-tree may be preferable when point lookups dominate and storing payloads internally allows searches to finish before reaching a leaf. In practice, B+ trees are often preferred for both point and range workloads because their storage layout supports scans particularly well.

Common Pitfalls and Interview Tips

  • Do not say that a B+ tree stores no keys internally; it stores separator keys internally but normally keeps all user-visible records in leaves.

  • Do not assume leaf keys are unique copies of internal separators; separator representation varies by implementation.

  • Both structures are balanced multiway trees, not binary trees.

  • The logarithmic lookup bound depends on the tree remaining balanced and on a bounded fanout.

  • Common follow-up questions involve node splitting and merging, underflow handling, write amplification, concurrency, and the effect of increasing fanout on disk I/O.

27

Which data structures can implement a Priority Queue?

A priority queue is an abstract collection that removes elements according to priority rather than insertion order. Common implementations include binary heaps, sorted and unsorted arrays, balanced search trees, and pairing heaps.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Operations

A typical priority queue supports:

  • Push: Insert an element with a given priority.

  • Pop: Remove and return the highest-priority element.

  • Peek: Return that element without removing it.

  • Is empty: Check whether the queue contains any elements.

The priority direction must be consistent. A min-priority queue removes the smallest priority, while a max-priority queue removes the largest.

Implementation Options

Implementation Push Pop Minimum Peek Space
Binary heap O(1) best; O(1) average for randomly ordered keys; O(log n) worst O(1) best; O(log n) average and worst O(1) O(n) stored; O(1) auxiliary
Sorted array O(1) best when the new element belongs at a removable end; O(n) average and worst otherwise O(1) if the minimum is stored at a removable end O(1) O(n) stored; O(1) auxiliary
Unsorted array O(1) best and amortized average; O(n) worst during resizing O(n) O(n) O(n) stored; O(1) auxiliary
Balanced search tree O(log n) O(log n) O(log n) O(n) stored; O(log n) recursive stack or O(1) iterative
Pairing heap O(1) amortized O(log n) amortized; O(n) worst O(1) O(n) stored; O(1) auxiliary
  • Binary heap: Insertion and removal follow a root-to-leaf path, while peeking accesses the root directly.

  • Sorted array: Insertion may shift many elements. Minimum removal is constant-time only when the minimum is at a removable end; removing index 0 from a conventional ascending list costs O(n).

  • Unsorted array: Insertion is inexpensive, but finding the minimum requires a linear scan.

  • Balanced search tree: Operations follow a path of height O(log n). Recursive implementations use an O(log n) stack; iterative implementations can use O(1) auxiliary space.

  • Pairing heap: Insertion and root access are cheap, while removing the root consolidates child heaps with an amortized logarithmic bound.

Let n be the number of queued entries. All implementations use O(n) total space for stored entries. Auxiliary space is additional working memory, and the original input is not counted.

Binary Heap Walkthrough

For a min-heap, consider pushing 5, 1, 3, and 2:

  1. After 5: [5].

  2. After 1: [1, 5].

  3. After 3: [1, 5, 3].

  4. After 2: [1, 2, 3, 5].

  5. Popping 1 moves the last element, 5, to the root, initially giving [5, 2, 3].

  6. Sifting 5 below its smaller child, 2, produces [2, 5, 3].

A heap array is not necessarily sorted; it only guarantees that each parent is no greater than its children.

Choosing an Implementation

  • Choose a binary heap for the usual insert-and-remove-minimum workload.

  • Choose a sorted array when ordered reads are frequent and insertions are rare.

  • Choose an unsorted array for simple prototypes where insertion dominates.

  • Choose a balanced search tree when ordered iteration, range queries, or duplicate-key management also matters.

  • Choose a pairing heap only when workload measurements justify its more complicated implementation.

  • In Python, the standard heapq module provides a binary heap. For equal priorities, (priority, sequence_number, payload) prevents Python from comparing payloads when priorities tie.

Common Pitfalls

  • Empty or single-element queues: pop() and peek() must handle an empty queue explicitly; removing the only element leaves an empty queue.

  • Duplicates and negative priorities: Both are valid and must be handled consistently.

  • Equal priorities: Removal order is unspecified unless a stable tie-breaker such as an insertion counter is used.

  • Off-by-one errors: In a zero-based binary heap, children are at 2 * index + 1 and 2 * index + 2.

  • Mutating input: Sorting a caller-owned list in place changes its order; copy it when preservation is required.

  • Already sorted input: It does not change individual heap-operation bounds, although constructing a heap bottom-up from n existing elements can be done in O(n).

  • Integer overflow: In fixed-width languages, calculate child indexes carefully for extremely large heaps.

28

How are binary tree traversal algorithms classified?

Tree traversal algorithms visit every node of a binary tree in a defined order. They are classified primarily as depth-first search (DFS) or breadth-first search (BFS), with DFS further divided into preorder, inorder, and postorder.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Classification

Algorithm Classification Visit rule Common use
Preorder Depth-first Visit the node before its subtrees Copying or serializing a tree
Inorder Depth-first Visit between the left and right subtrees Producing sorted values from a BST
Postorder Depth-first Visit the node after its subtrees Deleting a tree or computing subtree results
Level order Breadth-first Visit nodes one depth level at a time Finding shallow nodes or printing level by level

DFS follows a branch as deeply as possible before returning. BFS processes all nodes at one level before moving to the next.

Visit Orders

Consider this tree:

8
      /   \
     4     12
    / \    / \
   2   6  10  14
Traversal Visit order
Preorder 8, 4, 2, 6, 12, 10, 14
Inorder 2, 4, 6, 8, 10, 12, 14
Postorder 2, 6, 4, 10, 14, 12, 8
Level order 8, 4, 12, 2, 6, 10, 14

Inorder produces sorted output only when the input is a binary search tree (BST); it has no such guarantee for an arbitrary binary tree.

Complexity

Let n be the number of nodes, h the tree height, and w the maximum number of nodes on any level.

Approach Best time Average time Worst time Auxiliary space
DFS, recursive or iterative O(n) O(n) O(n) O(h)
BFS level order O(n) O(n) O(n) O(w)
  • Every node is visited once, giving O(n) time in all cases.

  • DFS space includes the recursion stack or explicit stack: O(h). For a balanced tree, h = O(log n); for a skewed tree, h = O(n).

  • BFS uses a queue containing up to O(w) nodes.

  • These auxiliary-space figures exclude the input tree and returned output. Storing all traversal results adds O(n) space.

  • Height convention: an empty tree has height -1, and a one-node tree has height 0.

Tree Types and Edge Cases

  • Binary tree: Each node has at most two children.

  • BST: A binary tree with a searchable ordering invariant, commonly left < node < right.

  • Complete tree: Every level is full except possibly the last, whose nodes are left-aligned.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has two children and all leaves have the same depth.

  • Balanced tree: At every node, the heights of the two subtrees differ by at most one.

The code handles an empty tree, one-node trees, duplicate values, and negative values. For a BST, inorder returns sorted values. Disconnected graphs and cycles are not valid binary-tree inputs; traversing a cyclic graph requires a separate visited-set strategy.

Code Example

from __future__ import annotations

from collections import deque


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def tree_traversals(root: TreeNode | None) -> dict[str, list[int]]:
    """Return recursive, iterative, and level-order binary tree traversals."""
    recursive_preorder: list[int] = []
    recursive_inorder: list[int] = []
    recursive_postorder: list[int] = []

    def visit_preorder(node: TreeNode | None) -> None:
        if node is None:
            return
        recursive_preorder.append(node.val)
        visit_preorder(node.left)
        visit_preorder(node.right)

    def visit_inorder(node: TreeNode | None) -> None:
        if node is None:
            return
        visit_inorder(node.left)
        recursive_inorder.append(node.val)
        visit_inorder(node.right)

    def visit_postorder(node: TreeNode | None) -> None:
        if node is None:
            return
        visit_postorder(node.left)
        visit_postorder(node.right)
        recursive_postorder.append(node.val)

    visit_preorder(root)
    visit_inorder(root)
    visit_postorder(root)

    iterative_preorder: list[int] = []
    stack: list[TreeNode] = []
    if root is not None:
        stack.append(root)

    while stack:
        node = stack.pop()
        iterative_preorder.append(node.val)
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

    iterative_inorder: list[int] = []
    stack = []
    current = root

    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        iterative_inorder.append(current.val)
        current = current.right

    iterative_postorder: list[int] = []
    stack: list[tuple[TreeNode, bool]] = []
    if root is not None:
        stack.append((root, False))

    while stack:
        node, children_visited = stack.pop()
        if children_visited:
            iterative_postorder.append(node.val)
            continue

        stack.append((node, True))
        if node.right is not None:
            stack.append((node.right, False))
        if node.left is not None:
            stack.append((node.left, False))

    level_order: list[int] = []
    queue: deque[TreeNode] = deque()
    if root is not None:
        queue.append(root)

    while queue:
        node = queue.popleft()
        level_order.append(node.val)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

    return {
        "recursive_preorder": recursive_preorder,
        "recursive_inorder": recursive_inorder,
        "recursive_postorder": recursive_postorder,
        "iterative_preorder": iterative_preorder,
        "iterative_inorder": iterative_inorder,
        "iterative_postorder": iterative_postorder,
        "level_order": level_order,
    }


root = TreeNode(
    8,
    TreeNode(4, TreeNode(2), TreeNode(6)),
    TreeNode(12, TreeNode(10), TreeNode(14)),
)

print(tree_traversals(root))
# Expected output:
# {'recursive_preorder': [8, 4, 2, 6, 12, 10, 14],
#  'recursive_inorder': [2, 4, 6, 8, 10, 12, 14],
#  'recursive_postorder': [2, 6, 4, 10, 14, 12, 8],
#  'iterative_preorder': [8, 4, 2, 6, 12, 10, 14],
#  'iterative_inorder': [2, 4, 6, 8, 10, 12, 14],
#  'iterative_postorder': [2, 6, 4, 10, 14, 12, 8],
#  'level_order': [8, 4, 12, 2, 6, 10, 14]}

Common Pitfalls

  • Do not confuse preorder, inorder, and postorder with level order.

  • Do not assume every binary tree is a BST or that inorder is always sorted.

  • In iterative postorder, a marker is needed to defer visiting a node until its children are processed.

  • Recursive traversal can exceed Python’s default recursion limit of about 1000 on skewed trees; use the iterative implementations or explicitly raise the limit.

  • Account for both the traversal stack or queue and the O(n) returned lists when calculating total space.

29

How can preorder traversal be implemented recursively in Python?

Preorder traversal visits a binary tree in root–left–right order. It processes the current node before recursively traversing its left subtree and then its right subtree.

Read full answer

Applies toPython 3.12

How It Works

For each node:

  1. Add the node’s value to the result.

  2. Recursively traverse the left subtree.

  3. Recursively traverse the right subtree.

This ordering applies to any binary tree; it does not require the tree to be a binary search tree.

Example Walkthrough

Consider this tree:

1
      / \
     2   3
    / \
   4   5
Step Node visited Result
1 1 [1]
2 2 [1, 2]
3 4 [1, 2, 4]
4 5 [1, 2, 4, 5]
5 3 [1, 2, 4, 5, 3]

The resulting preorder traversal is [1, 2, 4, 5, 3].

Complexity

Let n be the number of nodes and h the tree height measured in edges.

  • Time: O(n) in the best, average and worst cases, because every node is visited exactly once.

  • Auxiliary space: O(h) for the recursion stack. The input tree itself is not counted; counting it would make total space O(n).

  • A balanced tree has h = O(log n), while a completely skewed tree has h = O(n).

Code Example

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def preorder_traversal(root: TreeNode | None) -> list[int]:
    """Return the values of a binary tree in root-left-right order."""
    result: list[int] = []

    def visit(node: TreeNode | None) -> None:
        if node is None:
            return

        result.append(node.val)
        visit(node.left)
        visit(node.right)

    visit(root)
    return result


# Example:       1
#              /   \
#             2     3
#            / \
#           4   5
root = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3),
)

print(preorder_traversal(root))  # Expected output: [1, 2, 4, 5, 3]

Common Pitfalls

  • Incorrect order: Preorder is root, left, right—not left, root, right.

  • Empty tree: The function correctly returns [] when root is None.

  • Single node: It returns a list containing only that node’s value.

  • Duplicate values: Duplicates are preserved because traversal depends on node position, not value uniqueness.

  • Recursion depth: A deeply skewed tree can exceed Python’s default recursion limit of approximately 1,000 calls. For guaranteed support of arbitrary-depth trees, use an explicit stack.

  • Mutation: This implementation does not modify the tree, but it does allocate an O(n) output list, which is separate from the O(h) auxiliary stack.

30

How to implement binary tree preorder traversal without recursion?

Iterative preorder traversal visits a binary tree in the order root → left subtree → right subtree, using an explicit stack instead of recursion. This works for any binary tree and avoids recursion-depth issues for highly skewed trees.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm uses a LIFO stack to store nodes that still need to be visited:

  1. Create a stack containing the root.

  2. Pop the top node and append its value to the result.

  3. Push the node’s right child first, if it exists.

  4. Push the node’s left child second, if it exists.

  5. Repeat until the stack is empty.

Because a stack is last-in, first-out, pushing the right child before the left child ensures that the left subtree is processed first.

Preorder traversal is different from the other standard traversals:

  • Preorder: root, left, right

  • Inorder: left, root, right

  • Postorder: left, right, root

For a binary search tree, an inorder traversal produces values in sorted order. For an arbitrary binary tree, traversal order does not imply any sorting relationship.

Tree Types

The implementation applies to all binary-tree shapes:

  • Binary tree: Each node has at most two children.

  • Binary search tree: A binary tree whose left-subtree values are smaller and right-subtree values are larger than the node value, according to the tree’s duplicate-key policy.

  • Full binary tree: Every node has either zero or two children.

  • Perfect binary tree: Every internal node has two children, and all leaves are at the same depth.

  • Complete binary tree: All levels except possibly the last are full, and the last level is filled from left to right.

  • Balanced binary tree: For every node, the heights of its two subtrees differ by at most one under the standard definition.

Code Example

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def iterative_preorder(root: TreeNode | None) -> list[int]:
    """Return the binary tree's preorder traversal without recursion."""
    if root is None:
        return []

    result: list[int] = []
    stack: list[TreeNode] = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)

        # Push right first so that left is processed first.
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)

    return result


tree = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3),
)

print(iterative_preorder(tree))  # [1, 2, 4, 5, 3]

Example Walkthrough

For the tree:

1
      / \
     2   3
    / \
   4   5

The traversal proceeds as follows:

Step Node popped Result Stack after processing
1 1 [1] [3, 2]
2 2 [1, 2] [3, 5, 4]
3 4 [1, 2, 4] [3, 5]
4 5 [1, 2, 4, 5] [3]
5 3 [1, 2, 4, 5, 3] []

Complexity

Let n be the number of nodes and h the tree height, measured in edges.

  • Time complexity: O(n) in the best, average, and worst cases. Every node is pushed, popped, and appended exactly once.

  • Auxiliary space complexity: O(h) for the explicit stack, excluding the returned list. This is O(log n) for a balanced tree and O(n) for a completely skewed tree.

  • Output space: O(n) for the returned traversal list.

  • Input space: The input tree itself occupies O(n) space and is not counted as auxiliary space.

There is no recursion stack in this implementation.

Common Pitfalls

  • Pushing left before right: This produces root-right-left order instead of root-left-right.

  • Forgetting the empty-tree case: The function returns [] when root is None.

  • Handling other edge cases: A single-node tree returns [node.val]; duplicate and negative values are preserved; and the values being sorted does not affect preorder order.

  • Assuming the tree is a BST: Preorder is generally not sorted, even for a BST. Inorder traversal of a BST produces sorted values.

  • Using an invalid tree structure: The algorithm assumes a valid binary tree, which is connected and acyclic. Disconnected or cyclic inputs are outside the definition of a tree.

  • Confusing preorder with level order: Preorder follows depth-first traversal; level order uses breadth-first traversal with a queue.

  • Ignoring tree shape: The stack can grow to O(n) for a skewed tree, although the algorithm still avoids Python’s recursion-depth limit.

31

How do you convert a binary tree to a doubly linked list?

A binary tree-to-doubly-linked-list conversion uses an inorder traversal, reusing each tree node’s left and right pointers as the list’s previous and next links. The resulting list preserves the tree’s inorder sequence; it is sorted only when the original tree is a binary search tree.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

During an iterative inorder traversal:

  1. Push nodes onto a stack while descending through their left children.

  2. Pop the next node, which is the next node in inorder.

  3. Connect it to the previously visited node in both directions.

  4. Set the first node’s left pointer to None.

  5. Set the final node’s right pointer to None.

If previous is the previously visited node and current is the next node, the links become:

  • previous.right = current

  • current.left = previous

The original tree structure is modified rather than copied.

Example Walkthrough

For this tree:

4
       / \
      2   5
     / \
    1   3

The inorder traversal visits 1, 2, 3, 4, 5.

Node left after conversion right after conversion
1 None 2
2 1 3
3 2 4
4 3 5
5 4 None

Complexity

Let n be the number of nodes and h be the tree height in edges.

  • Time: O(n) in the best, average, and worst cases. Every node is pushed onto the stack, popped, and linked exactly once.

  • Auxiliary space: O(h) for the explicit traversal stack, excluding the input and output. A skewed tree can therefore require O(n) stack space.

  • Output space: O(n), because the linked list contains all n nodes. The existing nodes are reused, so there is no separate copy of the input tree.

  • There is no recursion stack in this implementation.

Code Example

from __future__ import annotations

from dataclasses import dataclass


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def tree_to_doubly_linked_list(root: TreeNode | None) -> TreeNode | None:
    """Convert a binary tree to a DLL using its inorder sequence."""
    if root is None:
        return None

    stack: list[TreeNode] = []
    current = root
    previous: TreeNode | None = None
    head: TreeNode | None = None

    while current is not None or stack:
        # Visit the leftmost unprocessed node.
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()

        # Reuse left and right as previous and next links.
        current.left = previous

        if previous is not None:
            previous.right = current
        else:
            head = current

        previous = current
        current = current.right

    # The final node must terminate the list.
    if previous is not None:
        previous.right = None

    return head


# Example call
tree = TreeNode(
    4,
    TreeNode(2, TreeNode(1), TreeNode(3)),
    TreeNode(5),
)

head = tree_to_doubly_linked_list(tree)
values: list[int] = []
current = head

while current is not None:
    values.append(current.val)
    current = current.right

print(values)  # [1, 2, 3, 4, 5]

Common Pitfalls

  • Wrong traversal order: Preorder or postorder produces a different sequence. Inorder is the standard conversion order.

  • Incorrect boundary links: The head’s left and tail’s right must both be None.

  • Unexpected mutation: The original tree’s child links are overwritten. Copy the nodes first if the tree must be preserved.

  • Assumed sorted values: A generic binary tree does not produce a sorted list; only a valid binary search tree does.

  • Edge cases: Empty trees return None, and a one-node tree produces a one-node list. Negative values and duplicates are preserved unchanged.

  • Invalid input: Cycles, disconnected components, and nodes with multiple parents are not valid binary trees and are not supported. A skewed tree is valid and is handled, although it can use O(n) stack space.

32

How do you build a binary expression tree from an arithmetic expression?

A binary expression tree represents an arithmetic expression so that operands are leaves and operators are internal nodes. The construction below uses the shunting-yard algorithm, respecting operator precedence, left associativity, parentheses, and unary signs while keeping every operator node strictly binary.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Construction Approach

The parser maintains two stacks:

  • Operands: a stack of TreeNode objects representing subexpressions.

  • Operators: a stack of operators that have not yet been attached to operands.

For each token:

  1. Push numbers directly onto the operand stack.

  2. Push ( onto the operator stack.

  3. For ), apply operators until the matching ( is reached.

  4. For an operator, first apply stacked operators with higher precedence. Operators with equal precedence are also applied when the incoming operator is left-associative.

  5. After all tokens are processed, apply the remaining operators.

The supported binary operators are +, -, *, and /. Unary + and - are normalized into binary nodes using 0 + value and 0 - value, so every operator node has two children.

Code Example

from __future__ import annotations

import re
from dataclasses import dataclass


@dataclass
class TreeNode:
    val: str
    left: TreeNode | None = None
    right: TreeNode | None = None


_TOKEN_PATTERN = re.compile(r"\d+(?:\.\d*)?|\.\d+|[()+\-*/]")


def build_expression_tree(expression: str) -> TreeNode | None:
    """Build a binary expression tree from an arithmetic expression."""
    if not expression.strip():
        return None

    tokens: list[str] = []
    position = 0

    for match in _TOKEN_PATTERN.finditer(expression):
        # Only whitespace may appear between valid tokens.
        if expression[position:match.start()].strip():
            raise ValueError("Expression contains an invalid character")
        tokens.append(match.group(0))
        position = match.end()

    if expression[position:].strip():
        raise ValueError("Expression contains an invalid character")

    operands: list[TreeNode] = []
    operators: list[tuple[str, bool]] = []  # (symbol, is_unary)
    expect_operand = True

    def precedence(symbol: str, is_unary: bool) -> int:
        if is_unary:
            return 3
        return {"+": 1, "-": 1, "*": 2, "/": 2}[symbol]

    def apply_operator() -> None:
        if not operators:
            raise ValueError("Malformed expression")

        symbol, is_unary = operators.pop()

        if is_unary:
            if not operands:
                raise ValueError("Unary operator is missing an operand")
            right = operands.pop()
            operands.append(TreeNode(symbol, TreeNode("0"), right))
        else:
            if len(operands) < 2:
                raise ValueError("Binary operator is missing an operand")
            right = operands.pop()
            left = operands.pop()
            operands.append(TreeNode(symbol, left, right))

    for token in tokens:
        if token[0].isdigit() or token[0] == ".":
            if not expect_operand:
                raise ValueError("Missing operator between operands")
            operands.append(TreeNode(token))
            expect_operand = False

        elif token == "(":
            if not expect_operand:
                raise ValueError("Missing operator before '('")
            operators.append(("(", False))

        elif token == ")":
            if expect_operand:
                raise ValueError("Empty parentheses or missing operand")
            if not operators or operators[-1][0] != "(":
                raise ValueError("Mismatched parentheses")

            while operators and operators[-1][0] != "(":
                apply_operator()

            operators.pop()  # Remove '('.
            expect_operand = False

        else:
            is_unary = token in {"+", "-"} and expect_operand

            if expect_operand and not is_unary:
                raise ValueError("Binary operator is missing its left operand")

            while operators and operators[-1][0] != "(":
                top_symbol, top_is_unary = operators[-1]
                top_precedence = precedence(top_symbol, top_is_unary)
                current_precedence = precedence(token, is_unary)

                should_apply = top_precedence > current_precedence
                if top_precedence == current_precedence:
                    # Binary operators are left-associative; unary signs
                    # are right-associative.
                    should_apply = not is_unary

                if not should_apply:
                    break

                apply_operator()

            operators.append((token, is_unary))
            expect_operand = True

    while operators:
        if operators[-1][0] == "(":
            raise ValueError("Mismatched parentheses")
        apply_operator()

    if len(operands) != 1:
        raise ValueError("Malformed expression")

    return operands[0]


expression = "3 + 4 * 2"
root = build_expression_tree(expression)
print(root.val, root.left.val, root.right.val, root.right.left.val, root.right.right.val)
# Expected output: + 3 * 4 2

Example Walkthrough

For 3 + 4 * 2:

  1. 3 becomes a leaf node.

  2. + is placed on the operator stack.

  3. 4 becomes another leaf node.

  4. * has higher precedence than +, so it is placed on the stack.

  5. 2 becomes the third leaf node.

  6. Applying * creates a subtree whose children are 4 and 2.

  7. Applying + creates the root whose children are 3 and the 4 * 2 subtree.

The resulting structure is:

  • Root: +

  • Left child: 3

  • Right child: *

  • Right child’s children: 4 and 2

Complexity

Let m be the expression length and k the number of tokens.

  • Time: O(m) in the best, average, and worst cases. The expression is scanned once, and each token is pushed and popped at most once.

  • Auxiliary space: O(k) for the token list and operand/operator stacks, excluding the input string and returned tree.

  • Output space: O(k) for the tree, with one node per number or operator plus an extra synthetic zero leaf per unary sign.

  • Recursion stack: O(1) because the implementation is iterative and is not limited by Python’s default recursion depth.

Common Pitfalls

  • Incorrect precedence: * and / must be evaluated before + and -.

  • Associativity: 8 - 3 - 2 means (8 - 3) - 2, so binary operators are left-associative.

  • Negative numbers: -3 is represented as 0 - 3 to preserve a strictly binary tree.

  • Malformed input: Empty expressions return None; invalid characters, adjacent operands, empty parentheses, and mismatched parentheses raise ValueError.

  • Single operands and duplicates: 42 produces one leaf, and repeated values produce separate nodes.

  • Evaluation is separate: This function constructs the tree; evaluation can be implemented later with a traversal.

  • Common follow-up: Interviewers may ask for preorder, inorder, postorder, or level-order traversal, or how to evaluate the tree without using the original string.

33

What is Morris Traversal for a Binary Tree?

Morris traversal is a binary-tree traversal technique that uses temporary thread pointers to traverse the tree without recursion or an explicit stack. The standard form produces the tree’s inorder sequence, visiting nodes in left, root, right order.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Morris traversal temporarily connects the rightmost node of a node’s left subtree back to that node. This creates a shortcut that allows the algorithm to return to the ancestor without storing it in a stack.

For each node with a left child:

  1. Find the rightmost node in its left subtree; this is the predecessor.

  2. If the predecessor’s right pointer is empty, create a temporary thread to the current node and move to the left child.

  3. If the predecessor’s right pointer already points to the current node, the left subtree has been visited. Remove the thread, visit the current node, and move right.

The temporary links are removed as the traversal continues, so the tree is restored to its original structure.

Complexity

Let n be the number of nodes and h the tree height.

Approach Time Auxiliary space Notes
Recursive inorder O(n) O(h) Includes the recursion stack
Iterative inorder with a stack O(n) O(h) Explicit stack stores ancestors
Morris inorder O(n) O(1) No recursion or explicit stack

Morris traversal is O(n) in the best, average and worst cases. Although there is a nested loop, each edge is traversed only a constant number of times.

The space complexity is O(1) excluding the input tree and output list. If the returned list is counted, total additional space is O(n). The input tree is not counted; it is temporarily modified but restored. For a balanced tree, h is O(log n), while for a completely skewed tree, h is O(n).

Code Example

from typing import Optional


class TreeNode:
    def __init__(
        self,
        val: int,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def morris_inorder(root: Optional[TreeNode]) -> list[int]:
    """Return the inorder traversal of a binary tree using Morris traversal."""
    result: list[int] = []
    current = root

    while current is not None:
        if current.left is None:
            # No left subtree: visit the node and continue right.
            result.append(current.val)
            current = current.right
        else:
            # Find the inorder predecessor of current.
            predecessor = current.left
            while (
                predecessor.right is not None
                and predecessor.right is not current
            ):
                predecessor = predecessor.right

            if predecessor.right is None:
                # Create a temporary thread back to current.
                predecessor.right = current
                current = current.left
            else:
                # Left subtree is complete; remove the temporary thread.
                predecessor.right = None
                result.append(current.val)
                current = current.right

    return result


# Example:
#        1
#       / \
#      2   3
#     / \
#    4   5
tree = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3),
)

print(morris_inorder(tree))  # Expected output: [4, 2, 5, 1, 3]

Example Walkthrough

Using the tree above, the inorder result is [4, 2, 5, 1, 3].

  1. At node 1, find predecessor 5 and set 5.right = 1; move left to 2.

  2. At node 2, find predecessor 4 and set 4.right = 2; move left to 4.

  3. Node 4 has no left child, so visit 4 and return to 2 through the thread.

  4. At node 2, detect that 4.right points back to 2; remove the thread, visit 2, and move to 5.

  5. Visit 5, return to 1 through its thread, remove that thread, and visit 1.

  6. Move to 3 and visit it, producing [4, 2, 5, 1, 3].

Common Pitfalls

  • Confusing Morris traversal with ordinary stack-based traversal: Morris temporarily modifies the tree’s right pointers.

  • Forgetting to remove threads: Always restore predecessor.right = None when the thread is encountered again.

  • Using the wrong predecessor: The predecessor is the rightmost node of the left subtree, not necessarily the left child.

  • Assuming the input is a binary search tree: Morris traversal works on any binary tree, but it does not produce sorted values unless the tree satisfies the BST ordering property.

  • Ignoring edge cases: The code handles an empty tree and a one-node tree. It also supports duplicate and negative values.

  • Assuming cycles are supported: The input must be a valid tree; cycles can cause infinite traversal. A single binary tree is connected by definition, so disconnected-graph handling is not applicable.

  • Recursion-limit concerns: Recursive traversal may exceed Python’s default recursion limit for deeply skewed trees, while Morris traversal avoids recursion entirely.

34

How does level-order traversal work in a binary tree?

Level-order traversal visits a binary tree in breadth-first order: the root first, then all nodes at the second depth, and then each subsequent depth. It uses a FIFO queue to track the nodes waiting to be processed.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A binary tree is a tree in which each node has at most two children, conventionally named left and right. Unlike a binary search tree, a general binary tree imposes no ordering requirement on the values.

The traversal follows these steps:

  1. Create an empty queue using collections.deque.

  2. Add the root to the queue if the tree is not empty.

  3. Remove the node at the front of the queue and record its value.

  4. Add its non-None left child, followed by its non-None right child.

  5. Repeat until the queue is empty.

Grouping each queue level separately produces a list of lists, where each inner list contains the values at one depth.

Example Walkthrough

Consider this tree:

1
      /   \
     2     3
    / \   / \
   4   5 6   7

The traversal proceeds as follows:

Depth Nodes visited Result
0 1 [1]
1 2, 3 [2, 3]
2 4, 5, 6, 7 [4, 5, 6, 7]

The resulting traversal is [[1], [2, 3], [4, 5, 6, 7]].

Complexity

For n nodes and maximum level width w:

  • Best-case time: O(n) — every node must still be visited.

  • Average-case time: O(n) — each node is enqueued and dequeued once.

  • Worst-case time: O(n) — the same operation occurs for every node.

  • Auxiliary space: O(w) — the queue contains at most one or two adjacent levels of nodes. The recursion stack is O(1) because the algorithm is iterative. The input tree is not counted.

  • Including the returned result: O(n) — the output stores every node value.

Using the convention that height counts edges, a tree with height h has levels 0 through h. In a balanced tree, h = O(log n); in a completely skewed tree, h = O(n - 1).

Applications

  • Processing by depth: Useful when operations differ by level, such as calculating the sum or average value at each depth.

  • Bottom-up analysis: The final level can be processed first to calculate subtree information upward.

  • Serialization: Breadth-first formats can encode a tree level by level, often using markers for missing children.

  • Tree transformations: Nodes can be grouped, reversed, or reorganized by depth.

  • Foundational BFS behavior: It demonstrates the same queue-based technique used in breadth-first search on graphs.

The algorithm works for complete, full, perfect, balanced, or irregular binary trees because it relies only on parent-child relationships.

Code Example

from __future__ import annotations

from collections import deque


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def level_order(root: TreeNode | None) -> list[list[int]]:
    """Return the values of a binary tree grouped by depth."""
    if root is None:
        return []

    result: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])

    while queue:
        level_size = len(queue)
        level_values: list[int] = []

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

            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)

        result.append(level_values)

    return result


root = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7)),
)

print(level_order(root))
# Expected output: [[1], [2, 3], [4, 5, 6, 7]]

Common Pitfalls

  • Using list.pop(0): Removing the first element from a Python list is O(n). Use collections.deque, whose front removal is O(1).

  • Losing level boundaries: Capture level_size before processing each level; otherwise, children from different depths can be mixed.

  • Assuming sorted values: Level-order traversal does not require a binary search tree or any particular ordering.

  • Ignoring edge cases: An empty tree returns [], a single-node tree returns [[value]], and duplicate values are preserved.

  • Misreporting space: The queue uses O(w) auxiliary space, while storing the complete output uses O(n) space.

35

How do BFS and DFS traverse binary trees?

BFS explores a binary tree level by level, while DFS follows a branch as deeply as possible before backtracking. Standard DFS produces preorder, inorder, and postorder traversals; standard BFS produces level-order traversal.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

BFS and DFS Roles

  • BFS: Uses a queue to visit nodes by increasing depth. Its standard binary-tree traversal is level order.

  • DFS: Uses a stack or recursion to explore descendants before moving to another branch. The visit position relative to the left and right children determines the traversal:

  • Preorder: visit the node, then its left and right subtrees.

  • Inorder: visit the left subtree, the node, then the right subtree.

  • Postorder: visit the left and right subtrees, then the node.

  • Recursive and iterative DFS produce the same ordering; only the storage mechanism differs.

Tree Terminology

These tree classifications are related but not interchangeable:

  • Binary tree: Each node has at most two children.

  • Binary search tree: Each node’s left subtree contains smaller keys and its right subtree contains larger keys.

  • Complete tree: Every level except possibly the last is full, and the last level is filled left to right.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has two children, and all leaves have the same depth.

  • Balanced tree: At every node, the heights of the two subtrees differ by at most one.

Example Visit Orders

Consider this tree:

8
       / \
      3   10
     / \    \
    1   6    14
Traversal Visit order
Preorder 8, 3, 1, 6, 10, 14
Inorder 1, 3, 6, 8, 10, 14
Postorder 1, 6, 3, 14, 10, 8
Level order 8, 3, 10, 1, 6, 14

For a binary search tree, inorder traversal visits its values in ascending order.

Complexity

Let n be the number of nodes, h the tree height, and w the maximum number of nodes on one level. Height counts edges, so an empty tree has height -1 and a single-node tree has height 0.

Method Best time Average time Worst time Auxiliary space
DFS O(n) O(n) O(n) O(h) for recursion or explicit stack
BFS O(n) O(n) O(n) O(w) for the queue

Each node is visited once, giving O(n) time. The input tree itself is not counted in auxiliary space. For a balanced tree, h = O(log n); for a skewed tree, h = O(n).

Code Example

from __future__ import annotations

from collections import deque
from dataclasses import dataclass
from typing import Literal

TraversalOrder = Literal["preorder", "inorder", "postorder"]


@dataclass(slots=True)
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


def dfs_recursive(
    root: TreeNode | None, order: TraversalOrder
) -> list[int]:
    """Return a recursive preorder, inorder, or postorder traversal."""
    if order not in ("preorder", "inorder", "postorder"):
        raise ValueError("Invalid traversal order")

    values: list[int] = []

    def visit(node: TreeNode) -> None:
        if order == "preorder":
            values.append(node.val)
            if node.left is not None:
                visit(node.left)
            if node.right is not None:
                visit(node.right)

        elif order == "inorder":
            if node.left is not None:
                visit(node.left)
            values.append(node.val)
            if node.right is not None:
                visit(node.right)

        else:
            if node.left is not None:
                visit(node.left)
            if node.right is not None:
                visit(node.right)
            values.append(node.val)

    if root is not None:
        visit(root)

    return values


def dfs_iterative(
    root: TreeNode | None, order: TraversalOrder
) -> list[int]:
    """Return an iterative DFS traversal using an explicit stack."""
    if root is None:
        return []
    if order not in ("preorder", "inorder", "postorder"):
        raise ValueError("Invalid traversal order")

    values: list[int] = []
    stack: list[tuple[TreeNode, int]] = [(root, 0)]

    while stack:
        node, state = stack.pop()

        if order == "preorder":
            values.append(node.val)
            if node.right is not None:
                stack.append((node.right, 0))
            if node.left is not None:
                stack.append((node.left, 0))

        elif order == "inorder":
            if state == 0:
                if node.right is not None:
                    stack.append((node.right, 0))
                stack.append((node, 1))
                if node.left is not None:
                    stack.append((node.left, 0))
            else:
                values.append(node.val)

        else:
            if state == 0:
                stack.append((node, 2))
                if node.right is not None:
                    stack.append((node.right, 0))
                if node.left is not None:
                    stack.append((node.left, 0))
            else:
                values.append(node.val)

    return values


def level_order(root: TreeNode | None) -> list[int]:
    """Return nodes in breadth-first, left-to-right level order."""
    if root is None:
        return []

    values: list[int] = []
    queue: deque[TreeNode] = deque([root])

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

        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)

    return values


root = TreeNode(
    8,
    TreeNode(3, TreeNode(1), TreeNode(6)),
    TreeNode(10, None, TreeNode(14)),
)

print(dfs_recursive(root, "preorder"))
# [8, 3, 1, 6, 10, 14]
print(dfs_recursive(root, "inorder"))
# [1, 3, 6, 8, 10, 14]
print(dfs_recursive(root, "postorder"))
# [1, 6, 3, 14, 10, 8]
print(dfs_iterative(root, "preorder"))
# [8, 3, 1, 6, 10, 14]
print(level_order(root))
# [8, 3, 10, 1, 6, 14]

Common Pitfalls and Interview Tips

  • Empty trees should return []; a single-node tree returns its value.

  • Duplicate and negative values are preserved exactly as stored. Sorted input does not change traversal mechanics.

  • Binary trees are connected and acyclic by definition. Disconnected or cyclic structures are invalid inputs; graph traversal would require a visited set.

  • Be explicit about whether height counts nodes or edges.

  • Recursive DFS can exceed Python’s default recursion limit on a skewed tree; the iterative version avoids that limitation.

  • Common follow-up questions include reconstructing a tree from traversal orders, finding the deepest node, and applying DFS or BFS to tree diameter, path finding, or shortest unweighted paths.

36

How do you implement a Map using a Binary Search Tree?

A Map implemented with a Binary Search Tree (BST) stores unique keys and their associated values. The BST ordering allows get, put, and remove to use the left and right subtrees for efficient lookup instead of scanning every entry.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

BST Invariants and Tree Types

A binary search tree requires each node to have at most two children and imposes an ordering between keys.

Structure Exact definition
Binary tree Every node has at most two children; keys have no required order.
Binary search tree For a key k, smaller keys are in the left subtree and larger keys are in the right subtree.
Complete binary tree Every level is full except possibly the last, which fills from left to right.
Full binary tree Every node has either zero or two children.
Perfect binary tree Every internal node has two children and all leaves have the same depth.
Balanced tree At every node, the subtree heights differ by at most one.

This implementation treats duplicate keys as an update to the existing value. It is not self-balancing, so sorted insertion can create a skewed tree.

Core Operations and Complexity

For n nodes and tree height h:

Operation Best Average Worst Auxiliary space
put O(1) O(log n) O(n) O(1)
get / contains O(1) O(log n) O(n) O(1)
remove O(1) O(log n) O(n) O(1)
items O(n) O(n) O(n) O(h), excluding output
  • Best case: The requested key is the root.

  • Average case: A balanced BST has h = O(log n).

  • Worst case: A skewed tree has h = O(n).

  • Storage: The map itself occupies O(n) space. No separate input collection is counted, and the iterative operations do not consume a recursion stack.

  • items uses O(h) traversal-stack space and returns O(n) output.

Walkthrough

Inserting pear, apple, and banana produces:

  1. pear becomes the root.

  2. apple < pear, so apple becomes the root’s left child.

  3. banana < pear, but banana > apple, so it becomes apple’s right child.

  4. Updating apple changes its value without changing the tree shape.

  5. Removing banana promotes its empty right subtree, leaving apple and pear.

Code Example

from dataclasses import dataclass
from typing import Generic, TypeVar

K = TypeVar("K")
V = TypeVar("V")


@dataclass(slots=True)
class TreeNode(Generic[K, V]):
    val: tuple[K, V]
    left: TreeNode[K, V] | None = None
    right: TreeNode[K, V] | None = None


class MapBST(Generic[K, V]):
    """An ordered map implemented with an unbalanced binary search tree."""

    def __init__(self) -> None:
        self.root: TreeNode[K, V] | None = None

    def put(self, key: K, value: V) -> None:
        """Insert a key or update its existing value."""
        if self.root is None:
            self.root = TreeNode((key, value))
            return

        current = self.root
        while True:
            current_key, _ = current.val

            if key < current_key:
                if current.left is None:
                    current.left = TreeNode((key, value))
                    return
                current = current.left
            elif key > current_key:
                if current.right is None:
                    current.right = TreeNode((key, value))
                    return
                current = current.right
            else:
                current.val = (key, value)
                return

    def get(self, key: K) -> V:
        """Return the value for key, or raise KeyError."""
        node = self._find(key)
        if node is None:
            raise KeyError(key)
        return node.val[1]

    def contains(self, key: K) -> bool:
        """Return whether key exists in the map."""
        return self._find(key) is not None

    def remove(self, key: K) -> None:
        """Remove key and its value, or raise KeyError."""
        found = self._find_with_parent(key)
        if found is None:
            raise KeyError(key)

        node, parent = found

        if node.left is None:
            self._replace_child(parent, node, node.right)
            return

        if node.right is None:
            self._replace_child(parent, node, node.left)
            return

        successor_parent = node
        successor = node.right
        while successor.left is not None:
            successor_parent = successor
            successor = successor.left

        node.val = successor.val
        self._replace_child(successor_parent, successor, successor.right)

    def items(self) -> list[tuple[K, V]]:
        """Return key-value pairs in ascending key order."""
        result: list[tuple[K, V]] = []
        stack: list[TreeNode[K, V]] = []
        current = self.root

        while current is not None or stack:
            while current is not None:
                stack.append(current)
                current = current.left

            current = stack.pop()
            result.append(current.val)
            current = current.right

        return result

    def _find(self, key: K) -> TreeNode[K, V] | None:
        current = self.root
        while current is not None:
            current_key, _ = current.val
            if key < current_key:
                current = current.left
            elif key > current_key:
                current = current.right
            else:
                return current
        return None

    def _find_with_parent(
        self, key: K
    ) -> tuple[TreeNode[K, V], TreeNode[K, V] | None] | None:
        parent: TreeNode[K, V] | None = None
        current = self.root

        while current is not None:
            current_key, _ = current.val
            if key < current_key:
                parent = current
                current = current.left
            elif key > current_key:
                parent = current
                current = current.right
            else:
                return current, parent

        return None

    def _replace_child(
        self,
        parent: TreeNode[K, V] | None,
        child: TreeNode[K, V],
        replacement: TreeNode[K, V] | None,
    ) -> None:
        if parent is None:
            self.root = replacement
        elif parent.left is child:
            parent.left = replacement
        else:
            parent.right = replacement


example = MapBST[str, int]()
example.put("pear", 4)
example.put("apple", 2)
example.put("banana", 3)
example.put("apple", 5)
example.remove("banana")
print(example.items())  # [('apple', 5), ('pear', 4)]

Common Pitfalls

  • Deletion with two children: Replace the node’s key-value pair with its inorder successor, then remove the successor from the right subtree.

  • Duplicate keys: The shown policy updates the existing value; another implementation could store duplicates separately.

  • Assuming O(log n) always: This BST does not rebalance, so sorted inputs can produce O(n) operations.

  • Recursion limits: Recursive deletion can overflow on deeply skewed trees; the iterative implementation avoids this.

  • Edge cases: Empty maps and missing keys are handled explicitly. One-node trees, duplicate keys, and negative keys also work correctly.

  • Interview follow-up: Interviewers commonly ask how to balance the tree using rotations, such as AVL or red-black trees, and how such balancing changes the worst-case complexity.

37

How do tree rotations rebalance a binary tree?

A tree rotation is a constant-time restructuring of a binary tree that changes local parent-child relationships while preserving the tree’s in-order sequence. Rotations are the fundamental operation used by AVL, red-black, treap, and splay trees to maintain their balancing invariants.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How a Rotation Works

A rotation moves a node’s child upward to become the new subtree root:

  • Right rotation: The left child becomes the new root; the original root becomes its right child.

  • Left rotation: The right child becomes the new root; the original root becomes its left child.

For example, right-rotating the following subtree around 30:

30
       /  \
     20    40
    /
   10

produces:

20
     /  \
   10    30
          \
           40

The sequence of operations is:

  1. Save root.left as the new subtree root, pivot.

  2. Move pivot.right into the original root’s left position.

  3. Make the original root the pivot’s right child.

  4. Return pivot so the caller can reconnect it to its parent.

The in-order sequence remains [10, 20, 30, 40]. Therefore, rotating a valid binary search tree (BST) preserves its sorted ordering.

Tree Types and Invariants

  • Binary tree: Every node has at most two children.

  • BST: A binary tree with a consistent ordering between left and right subtrees.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: A full tree in which all leaves have the same depth.

  • Complete tree: All levels except possibly the last are full, and the last level is filled from the left.

  • AVL-balanced tree: For every node, the heights of its left and right subtrees differ by at most one.

A rotation does not guarantee that a tree remains complete, full, or perfect. Its purpose is to preserve ordering while improving or maintaining a specific balance invariant.

Use Cases and AVL Rotation Cases

For an AVL tree, define the balance factor as:

balance factor = left subtree height - right subtree height

Heights here count edges, so an empty subtree has height -1.

Imbalance Shape Correction
Left-left (LL) Insertion or growth occurred in the left subtree’s left branch One right rotation
Right-right (RR) Insertion or growth occurred in the right subtree’s right branch One left rotation
Left-right (LR) Left subtree grew through its right branch Left rotation on the child, then right rotation on the root
Right-left (RL) Right subtree grew through its left branch Right rotation on the child, then left rotation on the root

Other common uses include:

  • Red-black trees: Rotations work with node recoloring to restore black-height invariants.

  • Treaps: Rotations restore heap priority while preserving BST ordering.

  • Splay trees: Rotations move a recently accessed node toward the root.

  • Balanced BST updates: Insertions and deletions may otherwise create increasingly deep paths.

Complexity

Operation Time Extra space Reason
One left or right rotation O(1) O(1) Only a fixed number of pointers change
Calculate height recursively O(n) O(h) Visits nodes and stores the recursion stack
Calculate balance factor O(n) O(h) Recursively computes subtree heights
AVL insertion or deletion O(log n) worst case O(h) The search path has logarithmic height; h = O(log n)

The input tree is not counted as extra space. For a skewed tree, h can be O(n). The iterative traversal in the example uses O(h) stack space without recursion-depth limitations.

Code Example

from __future__ import annotations


class TreeNode:
    """A node in a binary tree."""

    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def rotate_right(root: TreeNode | None) -> TreeNode | None:
    """Rotate a subtree right and return its new root."""
    if root is None or root.left is None:
        return root

    pivot = root.left
    root.left = pivot.right
    pivot.right = root
    return pivot


def rotate_left(root: TreeNode | None) -> TreeNode | None:
    """Rotate a subtree left and return its new root."""
    if root is None or root.right is None:
        return root

    pivot = root.right
    root.right = pivot.left
    pivot.left = root
    return pivot


def inorder_values(root: TreeNode | None) -> list[int]:
    """Return in-order values using an explicit stack."""
    values: list[int] = []
    stack: list[TreeNode] = []
    current = root

    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()
        values.append(current.val)
        current = current.right

    return values


root = TreeNode(
    30,
    left=TreeNode(20, left=TreeNode(10)),
    right=TreeNode(40),
)
balanced_root = rotate_right(root)

result = (
    inorder_values(balanced_root),
    balanced_root.val,
    balanced_root.left.val,
    balanced_root.right.val,
)
print(result)  # ([10, 20, 30, 40], 20, 10, 30)

Common Pitfalls

  • Losing the returned root: The new subtree root must be connected to the original parent.

  • Rotating in the wrong direction: Use a right rotation for LL and a left rotation for RR.

  • Assuming arbitrary trees are BSTs: Rotation preserves in-order sequence, but a malformed BST may still lack valid ordering.

  • Ignoring duplicate policy: Rotations preserve duplicates; the BST must separately define whether equal values go left, right, or both.

  • Edge cases: Empty and one-child subtrees are returned unchanged. Negative values behave like any other value, and already sorted input may produce a skewed tree.

  • Invalid structures: Disconnected graphs and cyclic structures are not valid binary trees and should be rejected before rotation.

  • Common follow-up: Interviewers often ask for a complete AVL insertion or deletion implementation, including height updates and all four imbalance cases.

38

What are threaded binary trees in data structures?

A threaded binary tree is a binary tree in which unused null child pointers are replaced with links to the node’s inorder predecessor or successor. Threading enables traversal without an explicit stack or recursion and allows predecessor/successor navigation in constant time when the required thread exists.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

In a normal binary tree, each node has two child pointers, and a null pointer indicates the absence of a child. In a threaded tree, some of those null pointers are repurposed:

  • A left thread points to the node’s inorder predecessor.

  • A right thread points to the node’s inorder successor.

  • Non-null pointers continue to point to actual children.

Threads do not change the tree’s logical contents; they only add navigation links. A threaded tree is not automatically a binary search tree: the values must satisfy the BST ordering property for ordinary value-based searching to be valid.

Types of Threading

Type Null pointers that are replaced Main benefit
Single-threaded Usually right threads pointing to inorder successors Inorder traversal without a stack
Fully inorder-threaded Left threads for predecessors and right threads for successors Both predecessor and successor access
Partially threaded Selected null pointers only Reduced modification overhead, but weaker navigation guarantees

The implementation usually distinguishes a thread from a child pointer using a separate flag, such as left_thread and right_thread, or by checking whether the pointer is null before threading.

Example and Traversal Orders

Consider this tree:

A
       / \
      B   C
       \   \
        D   E

Its ordinary traversal orders are:

  • Inorder: B, D, A, C, E

  • Preorder: A, B, D, C, E

  • Postorder: D, B, E, C, A

  • Level order: A, B, C, D, E

After inorder threading:

  • D receives a left thread to its predecessor, B.

  • D receives a right thread to its successor, A.

  • E receives a left thread to its predecessor, C.

  • The final node’s right thread and the first node’s left thread are usually null.

An inorder traversal can now follow right threads directly whenever a node has no right child. When a node has a real right child, the traversal finds the leftmost node in that subtree, which is the node’s successor.

Complexity

Let n be the number of nodes and h the tree height, where height counts edges.

  • Threading a tree: O(n) time, because every node is visited once.

  • Inorder traversal of a fully threaded tree: O(n) time and O(1) auxiliary space, excluding the input tree.

  • Inorder successor or predecessor: O(1) time when the appropriate thread or subtree pointer is directly available.

  • Recursive threading operation: O(h) recursion-stack space, in addition to the tree.

  • Iterative threading operation: O(1) auxiliary space if performed carefully with parent tracking.

  • Stored representation: A threaded tree uses O(n) total node storage, or potentially O(n) additional pointer/flag storage if separate thread fields are added to an existing tree.

For a balanced tree, h = O(log n); for a skewed tree, h = O(n).

Advantages and Limitations

Advantages:

  • Eliminates the need for a stack during inorder traversal.

  • Provides efficient predecessor and successor operations.

  • Can reduce recursion depth problems for very deep trees.

  • Supports repeated traversal without rebuilding the traversal state each time.

Limitations:

  • Requires additional flags or careful null-pointer conventions.

  • Insertions and deletions may require locating and updating affected threads.

  • Thread maintenance is more complex than in an ordinary binary tree.

  • It is most useful when predecessor/successor access or repeated inorder traversal is common.

Common Pitfalls

  • Confusing threads with children: A thread points to an ancestor-related predecessor or successor, not to a child.

  • Using threaded trees as BSTs without checking ordering: Threading improves navigation but does not guarantee sorted values.

  • Forgetting to update threads after insertion or deletion: Deleted nodes may leave stale predecessor/successor links.

  • Assuming every successor lookup is constant time: If a node has a real right child, finding its leftmost descendant may take O(h) time.

  • Ignoring the first and last nodes: Their missing predecessor or successor threads are normally null.

  • Interview follow-up: Interviewers commonly ask how inorder traversal works without recursion, how threads are updated during deletion, and how a threaded tree differs from a BST.

39

When is recursive binary tree traversal impractical?

Recursive tree traversal becomes impractical when tree depth can approach or exceed the runtime’s recursion limit, causing excessive call-stack usage or a RecursionError. This most often occurs with highly skewed or unbalanced trees, where depth grows linearly with the number of nodes.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

When Recursion Is Impractical

Recursive traversal is a poor fit when:

  • The tree is highly skewed: A tree resembling a linked list has height O(n), so recursive traversal may require one stack frame per node.

  • The depth exceeds the recursion limit: Python 3.12 normally raises RecursionError after roughly 1,000 nested calls, although the configured limit can vary.

  • Stack memory is constrained: Recursive traversal consumes the call stack in addition to the tree itself.

  • Many traversals run concurrently: Each traversal has its own call stack, multiplying peak memory usage.

  • The input is not trusted: A user-controlled structure could deliberately create excessive depth and trigger a denial-of-service condition.

Python does not perform general tail-call optimization, so moving the recursive call into the final position does not remove the stack requirement.

Tree Shape and Depth

The relevant tree categories must not be confused:

Tree type Exact definition
Binary tree Every node has at most two children, designated left and right.
Binary search tree A binary tree with the BST ordering property; a common duplicate policy is used separately.
Complete tree Every level except possibly the last is full, and the last level is filled from left to right.
Full tree Every node has either zero or two children.
Perfect tree Every internal node has two children, and all leaves have the same depth.
Balanced tree For every node, the heights of its left and right subtrees differ by at most one.

Using height measured in edges, an empty tree has height -1 and a one-node tree has height 0:

  • Balanced tree: h = O(log n)

  • Complete tree: h = O(log n)

  • Skewed tree: h = O(n)

Recursion depth depends on height, not directly on the total number of nodes. Therefore, a million-node balanced tree can be traversed recursively with modest stack usage, while a thousand-node skewed tree may already exceed Python’s default recursion limit.

Complexity

For a traversal that visits all n nodes:

  • Time: Best, average and worst case are all O(n) because every node is visited once.

  • Recursive auxiliary space: O(h) for the recursion stack.

  • Best case: O(log n) for a balanced tree.

  • Average case under a typical balanced or random-BST assumption: O(log n).

  • Worst case: O(n) for a skewed tree.

  • Iterative auxiliary space: O(h) for an explicit stack.

  • The tree itself is the input and is not counted as auxiliary space. If the code materializes the traversal in a list, that output requires another O(n) space, making total extra space O(n) in all shapes.

Small Walkthrough

Consider this binary tree, using an inorder traversal:

2
   / \
  1   3

An iterative traversal proceeds as follows:

Step Stack Output
1 [2] []
2 [2, 1] []
3 [2] [1]
4 [] [1, 2]
5 [3] [1, 2]
6 [] [1, 2, 3]

The recursive version follows the same visit order by completing the left subtree, visiting the node, and then completing the right subtree.

Code Example

The iterative implementation avoids Python’s recursion limit while preserving the same inorder result.

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def inorder_recursive(root: TreeNode | None) -> list[int]:
    """Return values in recursive inorder traversal order."""
    result: list[int] = []

    def visit(node: TreeNode | None) -> None:
        if node is None:
            return
        visit(node.left)
        result.append(node.val)
        visit(node.right)

    visit(root)
    return result


def inorder_iterative(root: TreeNode | None) -> list[int]:
    """Return values in iterative inorder traversal order."""
    result: list[int] = []
    stack: list[TreeNode] = []
    current = root

    while current is not None or stack:
        # Descend through the left spine, remembering each node.
        while current is not None:
            stack.append(current)
            current = current.left

        # Visit the next node in inorder.
        current = stack.pop()
        result.append(current.val)

        # Continue with its right subtree.
        current = current.right

    return result


root = TreeNode(2, TreeNode(1), TreeNode(3))

print(inorder_iterative(root))  # Expected output: [1, 2, 3]
print(inorder_recursive(root))  # Expected output: [1, 2, 3]

Common Pitfalls and Interview Tips

  • Off-by-one errors: State explicitly that this implementation uses height in edges and an empty-tree height of -1.

  • Mutating the input: The traversals only read left and right; they do not modify the tree.

  • Edge cases: Empty input returns []; one node returns its value; duplicates and negative values are preserved.

  • Already arranged values: Traversal reports the tree’s existing inorder sequence; it does not sort the tree.

  • Invalid structures: Cycles and disconnected components are not valid properties of a single binary tree and would require additional traversal safeguards.

  • Common follow-up: Interviewers may ask for preorder, postorder or level-order implementations, or why an iterative level-order traversal uses collections.deque and consumes O(w) space, where w is the tree’s maximum width.

40

What is the space complexity of storing a binary tree?

Space complexity for storing a binary tree with n nodes is O(n) under the standard model in which each node contains a fixed-size value and a fixed number of child references. This total includes the tree itself; auxiliary space depends on the operation, such as O(h) for DFS or O(w) for BFS.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Stored Tree Space

  • Node-based representation: Each node stores one value and references to its left and right children, requiring O(1) words per node when values have a fixed size.

  • Total space: For n nodes, the tree requires O(n) space.

  • Input counted: Yes. The total storage occupied by the tree is O(n).

  • Auxiliary space: Merely retaining an already constructed tree requires O(1) additional space.

  • Empty tree: O(1) space for the None root reference.

  • One-node tree: O(1) space.

  • Best, average, and worst cases: All are O(n) when complexity is measured by the number of stored nodes.

These bounds assume fixed-size node values. If values contain arbitrary-length data, such as large Python integers or byte strings, their total payload size must be added separately.

Space by Operation

Operation Time Auxiliary space Total space including tree
DFS traversal O(n) O(h) O(n + h) = O(n)
BFS traversal O(n) O(w) O(n + w) = O(n)
Search for an arbitrary value in an unsorted binary tree O(n) O(h) for iterative DFS O(n + h) = O(n)
  • DFS: An explicit stack holds at most O(h) pending nodes, where h is the tree height measured in edges.

  • For n ≥ 2, the minimum possible height of an n-node binary tree is O(log n).

  • The maximum possible height is O(n) for a completely skewed tree.

  • Actual stack usage can be smaller than h for a particular shape and push order.

  • An average case cannot be stated precisely without a model for tree shape and node distribution.

  • BFS: The queue holds up to O(w) nodes, where w is the maximum number of nodes on one level.

  • Best case: O(1) for a tree with only one node per level.

  • Worst case: O(n) for a wide tree.

  • Average case: Depends on the tree’s shape.

  • Unsorted-tree search: Because an ordinary binary tree has no ordering property, finding an arbitrary value generally requires visiting up to all n nodes, taking O(n) time. A search taking O(h) time applies to a binary search tree or to a search constrained to a known root-to-leaf path.

Effect of Tree Shape

The number of nodes determines total storage, so all standard binary-tree variants require O(n) space:

  • Binary tree: Each node has at most two children.

  • Complete binary tree: Every level is full except possibly the last, which is filled from left to right.

  • Full binary tree: Every node has either zero or two children.

  • Perfect binary tree: Every internal node has two children, and all leaves have the same depth.

  • Balanced binary tree: Under the common height-balanced definition, the heights of the two subtrees at every node differ by at most one.

Shape affects traversal workspace, not total node-storage complexity. A height-balanced tree has height O(log n), while a skewed tree can have height O(n).

Common Pitfalls

  • Do not confuse O(n) total tree storage with O(h) or O(w) auxiliary traversal space.

  • State whether the input tree is included in the space calculation.

  • Use one height convention consistently; here, height counts edges, so an empty tree has height -1.

  • Remember that recursive DFS consumes O(h) call-stack space and can exceed Python’s default recursion limit for highly skewed trees.

  • Do not assume an unsorted binary tree supports O(h) value searches; that guarantee belongs to a binary search tree.

41

How do you check whether a binary tree is full?

A binary tree is full when every node has either zero children or two children. A node with exactly one child makes the tree non-full. The check can be performed by traversing the tree and rejecting any node with exactly one child.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Algorithm

A binary tree is full if and only if, for every node:

  • It is a leaf, meaning both left and right are None; or

  • It is an internal node, meaning both left and right are not None.

The algorithm uses an iterative depth-first traversal:

  1. Start with the root in a stack.

  2. Remove one node from the stack.

  3. If the node has exactly one child, return False.

  4. Otherwise, add its children to the stack.

  5. If every node passes the check, return True.

The empty tree is conventionally considered full.

Related Tree Types

Tree type Definition
Binary tree Each node has at most two children, designated left and right.
Binary search tree A binary tree whose left-subtree values are smaller and right-subtree values are larger than the node’s value, assuming no duplicates.
Complete tree All levels except possibly the last are completely filled, and the last level is filled from left to right.
Full tree Every node has either zero or two children.
Perfect tree Every internal node has two children, and all leaves are at the same depth.
Balanced tree The heights of the left and right subtrees differ by at most one at every node, using the edge-based height convention.

A full tree does not have to be perfect or balanced. For example, a full tree can have leaves at different depths.

Code Example

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def is_full_binary_tree(root: TreeNode | None) -> bool:
    """Return True if every node has either zero or two children."""
    if root is None:
        return True

    stack: list[TreeNode] = [root]

    while stack:
        node = stack.pop()
        left = node.left
        right = node.right

        # Exactly one child means the tree is not full.
        if (left is None) != (right is None):
            return False

        if left is not None:
            stack.append(left)
        if right is not None:
            stack.append(right)

    return True


# Tree:
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3),
)

print(is_full_binary_tree(root))  # True

Step-by-step traversal of the example:

  1. Node 1 has two children, so it passes.

  2. Node 3 is a leaf, so it passes.

  3. Node 2 has two children, so it passes.

  4. Nodes 5 and 4 are leaves, so they pass.

  5. No node has exactly one child, so the result is True.

Complexity

Let n be the number of nodes and h be the tree height, counting edges from the root to the deepest leaf.

Case Time Space Reason
Best O(1) O(1) The root immediately violates the condition.
Average O(n) O(h) The traversal generally examines nodes until it finds a violation or finishes.
Worst O(n) O(h) A valid full tree requires checking every node.

The auxiliary space is O(h) for the explicit stack. The input tree itself is not counted. The iterative implementation avoids Python’s recursion-depth limit; a recursive implementation would also use O(h) call-stack space but could fail on a deeply skewed tree.

Common Pitfalls

  • Checking only the root is insufficient; every node must satisfy the full-tree condition.

  • A node with two children is valid even if the children have different subtree heights.

  • A node with exactly one child is an internal node and makes the tree invalid.

  • Do not confuse a full tree with a perfect tree: perfect trees additionally require all leaves to have the same depth.

  • Do not assume the tree is a binary search tree; fullness depends only on child counts, not value ordering.

  • An empty tree returns True by convention, while a one-node tree is a leaf and is therefore full.

  • Duplicate and negative val values do not affect the check. Input ordering and disconnected graphs are not applicable to binary-tree fullness.

  • The function assumes a valid rooted binary tree with no cycles; malformed cyclic input requires separate validation.

42

How do you recognize a perfect binary tree?

A perfect binary tree is a binary tree in which every internal node has exactly two children and all leaf nodes occur at the same depth. It is therefore both full and height-balanced, with a uniquely determined shape for a given height.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Defining Characteristics

Using height as the number of edges from the root to a deepest leaf:

  • Every internal node has exactly two children.

  • Every leaf is at the same depth.

  • A leaf has height 0; an empty subtree has height -1.

  • A perfect tree of height h contains exactly 2^(h+1) - 1 nodes.

  • A single-node tree is perfect because it has no internal nodes and one leaf at depth 0.

  • An empty tree is conventionally not perfect.

The node count alone is not enough: seven nodes can also form a taller, imperfect tree. Combined with the height, it is sufficient, because a tree of height h with exactly 2^(h+1) - 1 nodes has every level full.

Comparison with Other Binary Trees

Tree type Defining structure Perfect tree?
Binary tree Each node has at most two children Not necessarily
Binary search tree Left subtree values are smaller and right subtree values are larger Not necessarily
Complete tree All levels except possibly the last are full, and the last level is filled left to right Not necessarily
Full tree Every node has either zero or two children Not necessarily
Perfect tree Every internal node has two children and all leaves have equal depth Yes
Balanced tree At every node, subtree heights differ by at most one under the common definition Not necessarily; every perfect tree is balanced, but balance alone does not imply perfection

Fullness and equal leaf depth are both required. For example, a root whose left child has two leaf children but whose right child is a leaf is full, but it is not perfect.

Identifying a Perfect Binary Tree

Check the tree recursively in concept:

  1. A leaf is perfect.

  2. A node with exactly one child is not perfect.

  3. An internal node with two children is perfect only if both subtrees are perfect and have the same height.

  4. An empty subtree is not perfect.

For example:

1
      /   \
     2     3
    / \   / \
   4   5 6   7
  1. The root 1 has exactly two children.

  2. Nodes 2 and 3 each have exactly two children.

  3. Nodes 4, 5, 6, and 7 are leaves at the same depth, so the tree is perfect.

Complexity

For n nodes and tree height h:

  • Best-case time: O(1) when a one-child node is detected at the root before larger subtrees are visited.

  • Average-case time: O(n) when the first violation is uniformly distributed across node positions; without a specified input distribution, the average is not uniquely defined.

  • Worst-case time: O(n) because a perfect candidate requires examining every node.

  • Auxiliary space: O(h) for the explicit traversal and height stacks, excluding the input tree itself. For a perfect tree, h = O(log n); for a potentially skewed candidate, h = O(n).

Code Example

The iterative implementation avoids Python’s recursion-depth limit. It treats an empty tree as not perfect; if a problem defines the empty tree as perfect, change the initial None check to return True.

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def is_perfect(root: TreeNode | None) -> bool:
    """Return whether root is a perfect binary tree."""
    if root is None:
        return False

    # Each task is (node, phase):
    # phase 0 evaluates a node; phase 1 combines its children's heights.
    stack: list[tuple[TreeNode, int]] = [(root, 0)]
    heights: list[int] = []

    while stack:
        node, phase = stack.pop()

        if phase == 0:
            if node.left is None and node.right is None:
                heights.append(0)
            elif node.left is None or node.right is None:
                return False
            else:
                stack.append((node, 1))
                stack.append((node.right, 0))
                stack.append((node.left, 0))
        else:
            right_height = heights.pop()
            left_height = heights.pop()

            if left_height != right_height:
                return False

            heights.append(left_height + 1)

    return True


root = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7)),
)

print(is_perfect(root))  # True

Common Pitfalls

  • Confusing full with perfect: A full tree can have leaves at different depths.

  • Using node count alone: A count of 2^k - 1 nodes does not prove the shape is perfect; the tree’s height must also be exactly k - 1.

  • Confusing complete with perfect: A complete tree may have a partially filled final level.

  • Ignoring the empty-tree convention: State whether an empty tree is excluded.

  • Assuming values matter: Perfection is structural. Duplicate and negative values do not affect the result; BST ordering is a separate property.

  • Mixing height conventions: This answer counts height in edges, so a leaf has height 0.

A common interview follow-up asks whether every perfect tree is also complete, full, balanced, and a binary search tree. It is complete, full, and balanced by shape, but it is a binary search tree only if its values also satisfy the BST ordering rules.

43

What is the approach to serializing and deserializing a binary tree?

Serialization converts a binary tree into a lossless string, while deserialization reconstructs the original tree from that string. A common approach uses level-order traversal and a null marker such as # to preserve the position of every missing child.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

This solution works with any binary tree, not only a binary search tree. It does not assume that values are ordered, unique, or positive.

  • Serialize the tree using breadth-first search with collections.deque.

  • Write each non-null node’s value, followed by its left and right child positions.

  • Write # for a null child.

  • During deserialization, read the encoded values in the same order and rebuild the tree using another queue.

  • Null markers are essential because they preserve the tree’s shape, not just its values.

For example:

1
      / \
     2   3
        /
       4

The level-order encoding is:

1,2,3,#,#,4,#,#,#

The # entries identify absent children in the exact positions required to reconstruct the tree.

Example Walkthrough

Step Encoded value Action
1 1 Create the root
2 2 Attach 2 as the root’s left child
3 3 Attach 3 as the root’s right child
4 # Node 2 has no left child
5 # Node 2 has no right child
6 4 Attach 4 as node 3’s left child
7 # Node 3 has no right child
8 # Node 4 has no left child
9 # Node 4 has no right child

An empty tree is represented by the empty string. A tree containing only one node is represented by value,#,#.

Code Example

from __future__ import annotations

from collections import deque


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def serialize(root: TreeNode | None) -> str:
    """Serialize a binary tree using level-order traversal."""
    if root is None:
        return ""

    queue: deque[TreeNode | None] = deque([root])
    parts: list[str] = []

    while queue:
        node = queue.popleft()

        if node is None:
            parts.append("#")
            continue

        parts.append(str(node.val))
        queue.append(node.left)
        queue.append(node.right)

    return ",".join(parts)


def deserialize(data: str) -> TreeNode | None:
    """Deserialize a level-order encoded binary tree."""
    if not data:
        return None

    tokens = data.split(",")

    def parse_value(token: str, position: int) -> int | None:
        if token == "#":
            return None

        try:
            return int(token)
        except ValueError as error:
            raise ValueError(
                f"Invalid token at position {position}: {token!r}"
            ) from error

    root_value = parse_value(tokens[0], 0)
    if root_value is None:
        raise ValueError("The root cannot be a null marker")

    root = TreeNode(root_value)
    queue: deque[TreeNode] = deque([root])
    index = 1

    while queue and index < len(tokens):
        node = queue.popleft()

        left_value = parse_value(tokens[index], index)
        index += 1
        if left_value is not None:
            node.left = TreeNode(left_value)
            queue.append(node.left)

        if index >= len(tokens):
            raise ValueError("Missing right-child token")

        right_value = parse_value(tokens[index], index)
        index += 1
        if right_value is not None:
            node.right = TreeNode(right_value)
            queue.append(node.right)

    if queue or index != len(tokens):
        raise ValueError("Incomplete or extra serialized data")

    return root


tree = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3, left=TreeNode(4)),
)

serialized = serialize(tree)
print(serialized)  # 1,2,3,#,#,4,#,#,#

restored = deserialize(serialized)
assert serialize(restored) == serialized

Complexity

Let n be the number of nodes and w the maximum width of the tree.

  • Serialization time: O(n), because each node and each null child position is processed once.

  • Deserialization time: O(n), because each encoded token is processed once.

  • Serialization space: O(n) for the output string, plus O(w) for the queue. The input tree itself is not counted.

  • Deserialization space: O(n) for the token list and reconstructed tree, plus O(w) for the queue. The serialized input string itself is not counted.

This iterative BFS implementation avoids recursion-depth problems. A depth-first implementation would use O(h) stack space, where h is the tree height; h is O(log n) for a balanced tree and O(n) for a skewed tree.

Common Pitfalls

  • Omitting null markers: Encoding only node values loses the tree’s shape and cannot distinguish different trees with the same values.

  • Using inconsistent traversal orders: The deserializer must use the same order as the serializer.

  • Failing to validate input: Malformed encodings can produce missing children or extra nodes; the implementation raises ValueError for invalid data.

  • Confusing tree types: This format works for general binary trees. It does not imply the BST, complete, full, perfect, or balanced properties.

  • Edge cases: Empty trees, one-node trees, duplicate values, and negative values are supported. Already-sorted input, disconnected graphs, and cycles are not applicable to a binary tree.

44

How to check whether a binary tree is height-balanced?

A binary tree is height-balanced when, at every node, the heights of its left and right subtrees differ by at most one. This is a local condition: checking only the root is insufficient.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Use a bottom-up traversal. For each node:

  1. Obtain the height of its left and right subtrees.

  2. Compare those heights.

  3. Mark the node as balanced if the difference is at most 1 and both child subtrees are balanced.

  4. Compute the node’s height as 1 + max(left_height, right_height).

The implementation below uses an explicit stack, avoiding Python’s recursion-depth limit for highly skewed trees.

The height convention is:

  • Empty tree: -1

  • Leaf node: 0

  • Height counts edges on the longest downward path.

Related Tree Properties

Property Exact meaning
Binary tree Each node has at most two children
Height-balanced tree At every node, left and right subtree heights differ by at most one
Complete tree Every level except possibly the last is full, and the last level is filled from left to right
Full tree Every node has either zero or two children
Perfect tree All internal nodes have two children and all leaves are at the same depth
Binary search tree A binary tree with the BST ordering property; it need not be height-balanced

These properties are independent. For example, a binary search tree may be severely skewed.

Code Example

from __future__ import annotations

from dataclasses import dataclass


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


@dataclass
class _Frame:
    node: TreeNode
    stage: int = 0
    left_height: int = -1
    right_height: int = -1
    left_balanced: bool = True
    right_balanced: bool = True


def is_height_balanced(root: TreeNode | None) -> bool:
    """Return whether every node's child subtree heights differ by at most one."""
    if root is None:
        return True

    stack: list[_Frame] = [_Frame(root)]
    root_balanced = True

    while stack:
        frame = stack[-1]

        if frame.stage == 0:
            frame.stage = 1
            if frame.node.left is not None:
                stack.append(_Frame(frame.node.left))
            continue

        if frame.stage == 1:
            frame.stage = 2
            if frame.node.right is not None:
                stack.append(_Frame(frame.node.right))
            continue

        left_height = frame.left_height
        right_height = frame.right_height

        is_balanced = (
            frame.left_balanced
            and frame.right_balanced
            and abs(left_height - right_height) <= 1
        )
        height = 1 + max(left_height, right_height)

        stack.pop()

        if stack:
            parent = stack[-1]
            if parent.node.left is frame.node:
                parent.left_height = height
                parent.left_balanced = is_balanced
            else:
                parent.right_height = height
                parent.right_balanced = is_balanced
        else:
            root_balanced = is_balanced

    return root_balanced


tree = TreeNode(
    1,
    TreeNode(2, TreeNode(4, TreeNode(5))),
    TreeNode(3),
)

print(is_height_balanced(tree))  # False

Example Walkthrough

For the tree containing values 1, 2, 3, 4, and 5:

Node Left height Right height Difference Result
5 -1 -1 0 Balanced; height 0
4 0 -1 1 Balanced; height 1
2 1 -1 2 Not balanced; height 2
3 -1 -1 0 Balanced; height 0
1 2 0 2 Not balanced; height 3

The entire tree is therefore not height-balanced.

Complexity

For n nodes and tree height h, measured in edges:

  • Time: O(n) in the best, average, and worst cases. This implementation visits every node exactly once and performs constant work per node.

  • Auxiliary space: O(h) for the explicit DFS stack, excluding the input tree. An empty tree uses O(1) space. A balanced tree has h = O(log n), while a skewed tree has h = O(n).

Common Pitfalls

  • Checking only the root misses imbalance deeper in the tree.

  • Confusing height-balanced with complete, full, perfect, or balanced BST.

  • Using inconsistent height conventions; this implementation uses -1 for an empty subtree and 0 for a leaf.

  • Forgetting that the condition applies to every node, not merely adjacent levels.

  • Assuming all trees have logarithmic height; only height-balanced trees have h = O(log n).

  • A common follow-up asks for the balance factor of each node, which can be computed during the same traversal.

45

How do binary trees support IP routing and address lookup?

Binary trees provide efficient hierarchical prefix lookup in networking, especially through binary tries, which allow routers to match a destination IP address against CIDR routes and select the longest-prefix match.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Networking Applications

  • IP forwarding: A router stores connected networks, static routes, and dynamically learned routes in a forwarding table. Prefix structures accelerate the lookup of the best route for each destination address.

  • Longest-prefix matching: If an address matches 10.0.0.0/8 and 10.1.0.0/16, the more specific /16 route wins. Binary tries naturally track every prefix along the address’s bit path.

  • Address hierarchies: CIDR prefixes represent address ranges and allow route summarization, such as replacing several contiguous /24 routes with one /16.

  • Packet classification: Access-control lists and policy rules can be organized by address prefixes, ports, or protocol fields using tries or decision trees.

  • Name lookup: DNS implementations may use tries to match domain-name labels hierarchically.

These lookup structures are distinct from the algorithms that calculate routes. For example, Dijkstra’s algorithm may use a binary heap internally, while BGP and OSPF are primarily graph-based protocols.

Binary Tree Types

Structure Defining property Networking relevance
Binary tree Each node has at most two children General basis for prefix trees
Binary search tree Under a chosen duplicate policy, left keys are smaller and right keys are larger Can index sorted data, but requires augmentation for prefix matching
Complete tree Every level except possibly the last is full, and the last level is filled left to right Useful for array-based implementations
Full tree Every node has either zero or two children Defines full-tree shape, not prefix ordering
Perfect tree Every internal node has two children and all leaves have the same depth Maximum nodes for a given height
Balanced tree At every node, subtree heights differ by at most one, as in an AVL tree Guarantees logarithmic height
Binary trie Paths represent bits or characters; it is not ordered like a binary search tree Directly represents IP prefixes

A radix trie compresses single-child paths. A Patricia trie is a compressed binary trie that stores only branching nodes and prefixed edge labels.

Longest-Prefix Lookup

For IPv4, each address is treated as 32 bits. During lookup, the router follows the address’s zero or one bit at a time and remembers the most specific route encountered.

Example routes:

  1. 0.0.0.0/0 selects internet.

  2. 10.0.0.0/8 selects corporate.

  3. 10.1.0.0/16 selects datacenter.

For 10.1.2.3, lookup encounters the /8 route and then the more specific /16 route. It returns datacenter.

Complexity

Let n be the number of routes, B the address width, M the number of trie nodes, h the binary-tree height, and w the maximum width.

Operation or structure Time Space
Uncompressed trie insertion O(B) because at most B bits are traversed Up to O(nB) total; a new route creates at most B nodes
Trie lookup Best O(1) for an empty or immediately resolved table; average and worst O(B) because up to B bits are followed O(1) auxiliary space, excluding the stored trie
Patricia trie O(B) lookup and insertion O(n) nodes because shared paths are compressed
Ordinary binary search tree lookup Best O(1), average O(log n) for random insertion, worst O(n) for a skewed tree O(1) auxiliary lookup space
General tree traversal O(n) because every node is visited DFS uses O(h) including recursion stack; BFS uses O(w)

For a balanced tree, h = O(log n); for a skewed tree, h = O(n). The implementation below is iterative, so it is not constrained by Python’s recursion limit.

Code Example

from __future__ import annotations

from ipaddress import IPv4Address, IPv4Network


class TreeNode:
    """One node in a binary trie; val stores an associated route."""

    val: str | None
    left: TreeNode | None
    right: TreeNode | None

    def __init__(self, val: str | None = None) -> None:
        self.val = val
        self.left = None
        self.right = None


class BinaryRoutingTable:
    """Store IPv4 CIDR routes and perform longest-prefix matching."""

    def __init__(self) -> None:
        self.root = TreeNode()

    @staticmethod
    def _bits(address: str) -> str:
        """Convert a validated IPv4 address into 32 binary digits."""
        packed = IPv4Address(address).packed
        return "".join(f"{byte:08b}" for byte in packed)

    def insert(self, prefix: str, route: str) -> None:
        """Insert a CIDR route; an existing identical prefix is replaced."""
        network = IPv4Network(prefix, strict=False)
        node = self.root

        # Only the first prefixlen bits identify the route.
        for bit in self._bits(str(network.network_address))[: network.prefixlen]:
            if bit == "0":
                if node.left is None:
                    node.left = TreeNode()
                node = node.left
            else:
                if node.right is None:
                    node.right = TreeNode()
                node = node.right

        node.val = route

    def lookup(self, address: str) -> str | None:
        """Return the route with the longest matching prefix, if any."""
        node = self.root
        matched_route = node.val

        for bit in self._bits(address):
            child = node.left if bit == "0" else node.right
            if child is None:
                break

            node = child
            if node.val is not None:
                matched_route = node.val

        return matched_route


routes = BinaryRoutingTable()
routes.insert("0.0.0.0/0", "internet")
routes.insert("10.0.0.0/8", "corporate")
routes.insert("10.1.0.0/16", "datacenter")

print(routes.lookup("10.1.2.3"))  # datacenter

Common Pitfalls

  • Choosing the first match rather than the longest match: This is the most common routing-lookup error.

  • Ignoring prefix length: A /16 is more specific than a /8 even though it contains fewer addresses.

  • Confusing a trie with a binary search tree: Trie paths encode prefixes; binary search trees encode key ordering.

  • Overlooking duplicates: The example replaces the route for an identical prefix, matching simple routing-table behavior.

  • Ignoring real routing policy: Longest-prefix matching alone does not handle route metrics, administrative distance, or equal-cost multipath.

  • Using a highly skewed tree: An unbalanced binary search tree can degrade lookup from average O(log n) to worst-case O(n).

46

How is a path sum calculated in a binary tree?

In a binary tree, a path sum is usually the sum of node values along a path from the root to a leaf. It is calculated by carrying the running sum while traversing the tree, adding each node’s value, and checking the total when a leaf is reached.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

For a node node with an incoming sum prefix_sum, the sum including the current node is:

current_sum = prefix_sum + node.val

At a leaf, current_sum is a complete root-to-leaf path sum. At an internal node, traversal continues to both children with current_sum as the new prefix.

The standard path-sum problem asks whether at least one root-to-leaf path has a target sum. A related variation calculates the sum of all root-to-leaf paths.

Calculation Example

Consider this tree:

5
       / \
      2   3
     / \   \
    1   4   6

The root-to-leaf paths and their sums are:

Path Calculation Sum
5 → 2 → 1 5 + 2 + 1 8
5 → 2 → 4 5 + 2 + 4 11
5 → 3 → 6 5 + 3 + 6 14

The total of all path sums is 8 + 11 + 14 = 33. A target check for 11 returns True, while a target check for 10 returns False.

Code Example

The following implementation uses an explicit stack, so it avoids Python’s recursion-depth limit for highly skewed trees.

class TreeNode:
    def __init__(
        self,
        val: int,
        left: "TreeNode | None" = None,
        right: "TreeNode | None" = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def path_sums(root: TreeNode | None) -> list[int]:
    """Return the sums of all root-to-leaf paths."""
    if root is None:
        return []

    result: list[int] = []
    stack: list[tuple[TreeNode, int]] = [(root, 0)]

    while stack:
        node, prefix_sum = stack.pop()
        current_sum = prefix_sum + node.val

        if node.left is None and node.right is None:
            result.append(current_sum)
            continue

        # Push right first so the left subtree is processed first.
        if node.right is not None:
            stack.append((node.right, current_sum))
        if node.left is not None:
            stack.append((node.left, current_sum))

    return result


def has_path_sum(root: TreeNode | None, target: int) -> bool:
    """Return whether any root-to-leaf path sums to target."""
    if root is None:
        return False

    stack: list[tuple[TreeNode, int]] = [(root, 0)]

    while stack:
        node, prefix_sum = stack.pop()
        current_sum = prefix_sum + node.val

        if node.left is None and node.right is None:
            if current_sum == target:
                return True
            continue

        if node.right is not None:
            stack.append((node.right, current_sum))
        if node.left is not None:
            stack.append((node.left, current_sum))

    return False


tree = TreeNode(
    5,
    TreeNode(2, TreeNode(1), TreeNode(4)),
    TreeNode(3, None, TreeNode(6)),
)

print(path_sums(tree))          # [8, 11, 14]
print(has_path_sum(tree, 11))   # True
print(has_path_sum(tree, 10))   # False

Complexity

Let n be the number of nodes, h the tree height measured in edges, and L the number of leaves.

Operation Best time Average time Worst time Auxiliary space
Calculate all path sums O(n) O(n) O(n) O(h) for the stack
Check whether a target exists O(1) O(n) O(n) O(h) for the stack

path_sums must visit every node to collect every root-to-leaf sum. has_path_sum can stop early when it finds a matching leaf; its exact average case depends on where the target occurs.

The input tree is not counted in auxiliary space. The returned list additionally uses O(L) space, so total space including the output is O(h + L). For a balanced tree, h is O(log n); for a completely skewed tree, h is O(n).

Common Pitfalls

  • Checking internal nodes only: A complete path must end at a leaf.

  • Using the current sum as the result: The result is the sum accumulated from the root through the leaf.

  • Pruning based on a sum that is already too large: This is unsafe when node values can be negative.

  • Ignoring the empty tree: It has no paths, so the result is an empty list and target lookup returns False.

  • Forgetting the one-node case: The root is already a leaf, so its only path sum is root.val.

  • Assuming unique values: Duplicate values are valid and do not change the algorithm.

  • Treating sorted input as special: Input order does not affect path-sum calculation.

  • Adding visited logic for a binary tree: A valid binary tree is acyclic; a cycle indicates an invalid structure, not a different tree case.

  • Confusing path sum with arbitrary downward paths: The standard definition uses root-to-leaf paths, not every possible parent-to-descendant path.

47

What is the lowest common ancestor of two nodes in a binary tree?

The lowest common ancestor (LCA) of two nodes in a binary tree is the deepest node that is an ancestor of both targets. A node is considered an ancestor of itself, so if one target is an ancestor of the other, that target is the LCA.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Definition and Algorithm

In a general binary tree, the LCA can be found by:

  1. Searching for each target from the root.

  2. Recording its root-to-node path.

  3. Finding the longest common prefix of the two paths.

  4. Returning the last node in that common prefix.

The method does not depend on values being sorted, so it works for both a general binary tree and a binary search tree. It also compares node identity rather than stored values, making it safe when different nodes contain duplicate values.

If the targets do not exist in the tree, no LCA is defined. Interview problems commonly guarantee that both targets exist.

Binary Tree Context

A binary tree gives each node at most two children, conventionally named left and right. It imposes no ordering requirement on their values.

Other tree types are distinct:

  • Binary search tree: For every node, keys in its left subtree are smaller and keys in its right subtree are larger. A policy for duplicate keys must be defined separately.

  • Complete tree: Every level except possibly the last is full, and the last level’s nodes are positioned as far left as possible.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has exactly two children, and all leaves have the same depth.

  • Height-balanced tree: For every node, the heights of its left and right subtrees differ by at most one. Such a tree has height (O(log n)).

A binary search tree permits a different LCA algorithm that follows comparisons and takes (O(h)) time, where (h) is the tree height. That optimization does not apply to an unordered binary tree.

Walkthrough

Consider this tree:

Node Left child Right child
1 2 3
2 4 5
3 None None
4 None None
5 None None

The root-to-node paths are:

  • Node 4: 1 → 2 → 4

  • Node 5: 1 → 2 → 5

Their longest common prefix is 1 → 2, so the deepest shared node—and therefore the LCA—is node 2.

Complexity

Let n be the number of nodes and h the tree height, counting edges.

  • Best-case time: (O(1)), such as when both targets are the same root node and both paths are found immediately.

  • Average-case time: (O(n)), because the traversal may inspect a large portion of the tree.

  • Worst-case time: (O(n)), when the targets are near the ends of deep branches. Copying the two target paths adds at most (O(h)), which is absorbed by (O(n)).

  • Auxiliary space: (O(h)) for the DFS stack, current path, and saved target paths. The input tree itself is not counted.

For a balanced tree, (h = O(log n)); for a skewed tree, (h = O(n)). An iterative traversal avoids Python’s recursion-depth limit.

Common Pitfalls and Interview Tips

  • Depth off by one: If using node depths, place the root at depth 0; height and depth are not interchangeable.

  • Confusing values with identity: Pass the target nodes themselves rather than searching by value, because duplicate values may exist.

  • Ignoring ancestor cases: If one target is the other’s ancestor, or both targets are identical, the answer is that target.

  • Mutating the input: A path-based traversal should not need to restructure the tree.

  • Ignoring malformed trees: A valid binary tree is connected and acyclic. A visited set or cycle detection is needed only if malformed input containing cycles must be handled.

  • Integer overflow in other languages: If nodes are represented by integer indexes, ensure the type can hold every index and any computed depth.

  • Common follow-up: Interviewers may ask for the (O(h)) binary-search-tree solution, an iterative implementation, or how to extend LCA to a tree with more than two children per node.

48

Can inorder and preorder or postorder reconstruct a binary tree?

Yes, a binary tree can be reconstructed uniquely from inorder plus preorder or inorder plus postorder traversals, provided node values are distinct. The inorder traversal identifies the left and right subtrees, while the other traversal identifies each subtree’s root.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Reconstruction Logic

For every subtree:

  • Inorder visits left → root → right.

  • Preorder visits root → left → right, so its first value is the root.

  • Postorder visits left → right → root, so its last value is the root.

  • Find the root’s position in inorder:

  • Elements before it belong to the left subtree.

  • Elements after it belong to the right subtree.

  • The number of elements in the left subtree determines where the corresponding subtree begins in the preorder or postorder sequence.

For example:

Traversal Values
Preorder 8, 4, 2, 1, 6, 12, 10, 14
Inorder 1, 2, 4, 6, 8, 10, 12, 14
Postorder 1, 2, 6, 4, 10, 14, 12, 8

Reconstruction proceeds as follows:

  1. Preorder identifies 8 as the root; inorder splits the tree into left values [1, 2, 4, 6] and right values [10, 12, 14].

  2. The next preorder value, 4, is the left root; inorder splits its subtree into [1, 2] and [6].

  3. The next preorder value after the four-node left subtree, 12, is the right root.

  4. Postorder reconstruction follows the same partition, but each root is taken from the end of its postorder segment.

Code Example

The implementation uses an explicit stack, so it does not depend on Python’s recursion limit.

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def _inorder_positions(inorder: list[int]) -> dict[int, int]:
    positions: dict[int, int] = {}
    for index, value in enumerate(inorder):
        if value in positions:
            raise ValueError("Node values must be distinct for unique reconstruction.")
        positions[value] = index
    return positions


def build_from_inorder_preorder(
    inorder: list[int], preorder: list[int]
) -> TreeNode | None:
    """Reconstruct a binary tree from distinct inorder and preorder values."""
    if len(inorder) != len(preorder):
        raise ValueError("Traversals must contain the same number of nodes.")
    if not inorder:
        return None

    positions = _inorder_positions(inorder)
    if set(preorder) != set(inorder):
        raise ValueError("Traversals must contain the same node values.")

    root = TreeNode(preorder[0])
    # Each frame contains: node, inorder start/end, preorder start.
    stack: list[tuple[TreeNode, int, int, int]] = [
        (root, 0, len(inorder) - 1, 0)
    ]

    while stack:
        node, in_start, in_end, pre_start = stack.pop()
        root_index = positions[node.val]
        left_size = root_index - in_start

        # Push right first so the left subtree is processed first.
        if root_index < in_end:
            right_pre_start = pre_start + 1 + left_size
            node.right = TreeNode(preorder[right_pre_start])
            stack.append(
                (node.right, root_index + 1, in_end, right_pre_start)
            )

        if left_size > 0:
            left_pre_start = pre_start + 1
            node.left = TreeNode(preorder[left_pre_start])
            stack.append(
                (node.left, in_start, root_index - 1, left_pre_start)
            )

    return root


def build_from_inorder_postorder(
    inorder: list[int], postorder: list[int]
) -> TreeNode | None:
    """Reconstruct a binary tree from distinct inorder and postorder values."""
    if len(inorder) != len(postorder):
        raise ValueError("Traversals must contain the same number of nodes.")
    if not inorder:
        return None

    positions = _inorder_positions(inorder)
    if set(postorder) != set(inorder):
        raise ValueError("Traversals must contain the same node values.")

    root = TreeNode(postorder[-1])
    # Each frame contains: node, inorder start/end, postorder start/end.
    stack: list[tuple[TreeNode, int, int, int, int]] = [
        (root, 0, len(inorder) - 1, 0, len(postorder) - 1)
    ]

    while stack:
        node, in_start, in_end, post_start, post_end = stack.pop()
        root_index = positions[node.val]
        left_size = root_index - in_start

        # Push right first so the left subtree is processed first.
        if root_index < in_end:
            right_post_start = post_start + left_size
            right_post_end = post_end - 1
            node.right = TreeNode(postorder[right_post_end])
            stack.append(
                (
                    node.right,
                    root_index + 1,
                    in_end,
                    right_post_start,
                    right_post_end,
                )
            )

        if left_size > 0:
            left_post_end = post_start + left_size - 1
            node.left = TreeNode(postorder[left_post_end])
            stack.append(
                (
                    node.left,
                    in_start,
                    root_index - 1,
                    post_start,
                    left_post_end,
                )
            )

    return root


pre_tree = build_from_inorder_preorder(
    [1, 2, 4, 6, 8, 10, 12, 14],
    [8, 4, 2, 1, 6, 12, 10, 14],
)
post_tree = build_from_inorder_postorder(
    [1, 2, 4, 6, 8, 10, 12, 14],
    [1, 2, 6, 4, 10, 14, 12, 8],
)

print(pre_tree.val, pre_tree.left.val, pre_tree.right.val)
# Expected output: 8 4 12
print(post_tree.val, post_tree.left.val, post_tree.right.val)
# Expected output: 8 4 12

Complexity

Let n be the number of nodes and h the tree height in edges.

Operation Best time Average time Worst time Space
Inorder + preorder O(n) O(n) expected O(n²) O(n)
Inorder + postorder O(n) O(n) expected O(n²) O(n)
  • Time: Every node is processed once. In the best and average cases, dictionary lookups take O(1). If the dictionary suffers O(n) hash collisions per lookup or insertion, the worst-case time is O(n²).

  • Space: The position map and returned tree use O(n), while the explicit stack uses O(h). Input arrays are not counted. For a balanced tree, h is O(log n); for a skewed tree, it is O(n).

Common Pitfalls

  • Duplicate values: Different tree shapes can produce identical traversals. The code rejects duplicates to preserve the uniqueness guarantee.

  • Wrong root position: Preorder roots come from the beginning; postorder roots come from the end of the current subtree segment.

  • Off-by-one errors: Carefully track empty segments and subtree sizes.

  • Input mutation: The implementation only reads the traversal lists.

  • Edge cases: Empty input returns None; one-node and negative-value trees work; already ordered traversal values are valid inputs.

  • Graph concepts: Disconnected components and cycles do not apply to binary-tree reconstruction.

49

How do you check whether a binary tree is symmetric?

A binary tree is symmetric when its left and right subtrees are mirror images: corresponding nodes must have equal values, and their children must match in reversed positions. The root itself does not need a separate comparison because it is the center of the mirror.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Compare two nodes that should be mirrors of each other:

  • If both nodes are None, the corresponding regions match.

  • If only one node is None, the structures differ.

  • Otherwise, their values must match.

  • Compare left.left with right.right, and left.right with right.left.

Start by comparing the root’s left child with its right child.

Code Example

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def is_symmetric(root: TreeNode | None) -> bool:
    """Return True if the binary tree is a mirror image of itself."""

    def is_mirror(left: TreeNode | None, right: TreeNode | None) -> bool:
        if left is None and right is None:
            return True

        if left is None or right is None:
            return False

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

    if root is None:
        return True

    return is_mirror(root.left, root.right)


# Example tree:
#       1
#      / \
#     2   2
#    / \ / \
#   3  4 4  3
root = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(3),
        TreeNode(4),
    ),
    TreeNode(
        2,
        TreeNode(4),
        TreeNode(3),
    ),
)

print(is_symmetric(root))  # True

Example Walkthrough

For the tree above, the algorithm performs these comparisons:

Compared nodes Result
Left 2 and right 2 Values match
Left 3 and right 3 Values match
Left 4 and right 4 Values match
All corresponding child pairs Both are None

The function returns True.

Complexity

Let n be the number of nodes and h the tree height measured in edges.

  • Best-case time: O(1) for an empty tree or a tree with only a root.

  • Average-case time: O(n) because the comparison may examine a substantial portion of the tree.

  • Worst-case time: O(n) because every pair of mirrored nodes may need to be checked.

  • Auxiliary space: O(h) for the recursion stack. The input tree is not counted. For a balanced tree, h = O(log n); for a completely skewed tree, h = O(n).

The recursive implementation is concise, but a highly skewed tree can exceed Python’s default recursion limit. In production code, an explicit stack can be used instead.

Edge Cases and Common Pitfalls

  • Empty tree: An empty tree is considered symmetric.

  • One-node tree: It is symmetric.

  • Different shapes: If one side contains an extra node, the None mismatch detects it.

  • Different values: Corresponding nodes must have equal values.

  • Duplicate values: Duplicates are allowed; symmetry depends on both structure and values.

  • Do not compare ordinary child pairs: left.left must be compared with right.right, not with right.left.

50

How do binary decision trees support AI decision-making?

A binary decision tree represents a sequence of binary tests that progressively narrow a problem until reaching a decision. Each internal node contains a test, its two branches represent possible outcomes, and its leaves contain final class labels or predicted values.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Structure and Tree Types

A binary tree is any rooted tree in which each node has at most two children, conventionally named left and right. It is not necessarily a binary search tree because decision-tree nodes generally do not maintain sorted values.

Common tree types have distinct definitions:

  • Complete tree: Every level except possibly the last is full, and nodes on the last level occupy the leftmost positions.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has two children, and all leaves have the same depth.

  • Balanced tree: Under the common height-balanced definition, the left and right subtree heights differ by at most one at every node, giving height O(log n).

A decision tree need not be complete, full, perfect, balanced, or a binary search tree. Standard machine-learning decision trees may also use splits with more than two children, although the binary form described here has exactly two branches.

Learning and Using Decisions

During training, a decision-tree algorithm searches for useful splits of the training data. Common criteria include:

  • Information gain: Measures the reduction in entropy after a split.

  • Gini impurity: Commonly used by CART to choose a split that makes child nodes more homogeneous.

  • Mean squared error: Used when the tree performs regression rather than classification.

For a classification dataset S, entropy is:

[ H(S)=-sum_c p©log_2 p© ]

Information gain compares the parent’s entropy with the weighted entropy of its children. A greedy learner selects the split with the greatest gain at each node and continues recursively or iteratively.

Once trained, prediction follows one root-to-leaf path. The values encountered at each internal node determine which branch is taken. Classification leaves usually contain a class label, while regression leaves contain an average or another estimated numeric value.

Small Example

Consider an automated loan application:

  1. The root asks whether annual income is greater than $50,000.

  2. If not, the applicant goes to the review leaf.

  3. If yes, the next node asks whether the credit score is greater than 700.

  4. A score above 700 reaches the approve leaf.

  5. Otherwise, it reaches the review leaf.

For an applicant with $60,000 income and a credit score of 650, the root selects the right branch. The credit-score test then selects the left branch, producing review.

Complexity

Let n be the number of tree nodes, h the height measured in edges, m the number of training rows, d the number of candidate features, and c the number of distinct classes.

Operation Time Space
Entropy or Gini calculation O(m) because the labels must be counted O(c) auxiliary space, excluding the input
Prediction Best O(1); average O(h) for a balanced tree; worst O(n) for a skewed tree O(1) auxiliary space iteratively or O(h) recursion space recursively; input and stored tree excluded
Store or copy a trained tree O(n) to copy or materialize the nodes O(n) model space, excluding training input
Exhaustive CART training with presorted feature data supplied O(md) per visited node; best O(md) for a shallow tree; worst O(m²d) because up to O(m) nodes may each scan O(md) candidates O(n) model space plus O(h) recursion stack; add O(md) if presorted copies are created

There is no universal average training time because it depends on the resulting splits and training-data distribution. All space figures exclude the original input unless explicitly stated; auxiliary presorted copies and recursion stacks are included.

Common Pitfalls

  • Do not assume a binary tree is a binary search tree; decision trees are organized by selected splits.

  • Define threshold behavior explicitly, especially whether equality goes left or right.

  • Handle missing features, missing values, and empty branches consistently.

  • Deep trees can overfit; use validation, pruning, minimum leaf sizes, and maximum depth.

  • Small changes in training data can produce a different tree, so a single tree may be unstable. Random forests and gradient-boosted trees address this by combining or sequentially building multiple trees.

  • Regression trees produce piecewise-constant predictions learned from training targets; they generally do not extrapolate reliably beyond target values observed during training.

  • Common follow-up questions ask why trees overfit, how pruning works, how categorical features are handled, and how decision trees differ from random forests and boosted trees.

51

What role do binary trees play in mark-and-sweep garbage collection?

Binary trees provide a simple acyclic structure for tracing reachable objects, but real garbage collectors usually operate on general object graphs that may contain cycles and shared references. In mark-and-sweep, marking follows references from root objects, while sweeping removes every heap object that was not marked.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Role in Garbage Collection

A binary tree can represent a parent-child ownership hierarchy in which each object has at most two children. During the mark phase, the collector performs a graph traversal:

  1. Begin with root objects, which are usually stack variables, globals, or other live references.

  2. Mark each visited object as reachable.

  3. Follow its child references and continue until all reachable objects are marked.

  4. During the sweep phase, scan the heap and reclaim every unmarked object.

A strict binary tree cannot contain cycles, so a tree traversal alone would be sufficient. Real managed-memory systems model objects as a graph rather than a tree: one object may be referenced by multiple parents, and references may form cycles. Consequently, collectors normally use an identity-based visited set or a per-object mark bit to prevent repeated processing and infinite loops.

Binary Tree Variations

These definitions are distinct and should not be used interchangeably:

  • Binary tree: Every node has at most two children, conventionally named left and right.

  • Binary search tree: For every node, keys in its left subtree are smaller and keys in its right subtree are larger; duplicate-key rules must be specified separately.

  • Complete tree: Every level is full except possibly the last, and the last level is filled from left to right.

  • Full tree: Every node has either zero or two children.

  • Perfect tree: Every internal node has two children, and all leaves have the same depth.

  • Balanced tree: Subtree heights differ by at most one under the usual definition, resulting in height O(log n).

Only the binary-tree property is needed for mark-and-sweep. There is no requirement that the structure be complete, perfect, balanced, or a binary search tree.

Example Walkthrough

Consider this tree, where the heap also contains an unreachable object 99:

1
      / \
     2   3
    /
   4
Step Action Marked objects
1 Start from root 1 {1}
2 Follow references to 2 and 3 {1, 2, 3}
3 Follow 2 to 4 {1, 2, 3, 4}
4 Sweep the heap 99 is reclaimed

Complexity

Let n be the number of heap objects, v the number of reachable objects, and h the reachable structure’s height measured in edges.

  • Mark phase: O(v) time because each reachable object and its outgoing references are processed once.

  • Sweep phase: O(n) time because the collector scans the heap.

  • Total time: O(n) in the best, average, and worst cases; sweeping always scans all heap objects.

  • Auxiliary space: O(v + h) for the visited set and explicit DFS stack. For a binary tree, h is O(log n) when balanced and O(n) when skewed.

  • The input heap is not counted as auxiliary space. Counting it, total memory usage remains O(n).

Code Example

The following Python simulation uses an explicit stack, so it also handles highly skewed trees without hitting Python’s recursion limit.

from __future__ import annotations


class TreeNode:
    def __init__(
        self,
        val: int,
        left: TreeNode | None = None,
        right: TreeNode | None = None,
    ) -> None:
        self.val = val
        self.left = left
        self.right = right


def mark_and_sweep(
    roots: list[TreeNode],
    heap: list[TreeNode],
) -> list[TreeNode]:
    """Remove heap objects unreachable from the given roots."""
    marked: set[int] = set()
    stack: list[TreeNode] = list(roots)

    # Mark phase: traverse every reference reachable from the roots.
    while stack:
        node = stack.pop()

        # Object identity is required because equal values may be distinct.
        if id(node) in marked:
            continue

        marked.add(id(node))

        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)

    # Sweep phase: retain only marked objects.
    heap[:] = [node for node in heap if id(node) in marked]
    return heap


root = TreeNode(
    1,
    left=TreeNode(2, left=TreeNode(4)),
    right=TreeNode(3),
)
unreachable = TreeNode(99)
heap = [root, unreachable, root.left, root.right, root.left.left]

survivors = mark_and_sweep([root], heap)
print([node.val for node in survivors])
# Expected output: [1, 2, 3, 4]

Common Pitfalls

  • Assuming every object graph is a tree: Shared references and cycles require identity-based visited tracking.

  • Marking by value: Two distinct objects may have the same value, so id(node) or a per-object mark bit is safer.

  • Forgetting the roots: Objects reachable only from stack variables, globals, or active function frames remain live.

  • Using recursion without checking depth: A skewed tree can exceed Python’s default recursion limit; an explicit stack avoids that issue.

  • Confusing height conventions: This answer uses edges, so an empty tree has height -1 and a leaf has height 0.

  • Assuming Python uses only mark-and-sweep: CPython primarily uses reference counting and also has a cycle collector; the example simulates the algorithm rather than reproducing CPython’s complete implementation.

52

How do trie data structures implement autocomplete?

A trie (prefix tree) stores words by their character prefixes, allowing autocomplete to locate all words sharing a query prefix without scanning the entire corpus. After finding matching words, a production system ranks them using frequency, recency, popularity, or personalization signals.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • Insertion: Store each word along a path of character edges. Mark the final node as the end of a word and attach metadata such as its frequency.

  • Prefix lookup: Follow the characters of the requested prefix from the root. If an edge is missing, no suggestions exist.

  • Suggestion collection: Traverse the subtree below the matched prefix and collect its terminal nodes.

  • Ranking: Return the highest-scoring suggestions, usually limited to a small k.

  • Shared-prefix efficiency: Words such as cat, car, and cart share the path for ca.

For a small example, insert cat, car, cart, and dog. A query for ca follows the root through c and a, then finds cat, car, and the descendant cart. If their frequencies are 10, 20, and 30, the ranked result is cart, car, cat.

Complexity

Let:

  • T be the total number of characters in the indexed corpus.

  • p be the prefix length.

  • V be the number of trie nodes visited below the prefix.

  • C be the number of matching candidate words.

  • R be the total characters examined while constructing candidate words.

  • k be the number of returned suggestions.

Operation Best case Average case Worst case Space
Build trie O(T) O(T) O(T) O(T) auxiliary
Locate prefix O(p) O(p) O(p) O(1) working
Collect suggestions O(V) O(V) O(V) O(d) traversal stack
Rank candidates O(C log(k + 1)) O(C log(k + 1)) O(C log(k + 1)) O(k) heap entries

For a fixed alphabet, trie insertion is O(T) in all cases. Query cost is deterministic, so its average and worst cases are the same; the best case occurs when the prefix has no descendants. On an existing trie, query auxiliary space is O(d + k + H), where d is the remaining depth and H is the total storage for retained candidate strings. The indexed corpus, existing trie, and returned output are not counted as query auxiliary space.

Approach Time Space When to use
Linear corpus scan O(NL + R) O(k) with a top-k heap Small or infrequently queried corpora
Trie-based lookup O(p + V + R + C log(k + 1)) O(T) persistent plus O(d + k + H) per query Large corpora with frequent prefix queries

Code Example

from collections.abc import Iterator
from dataclasses import dataclass, field
from heapq import heappush, heapreplace


@dataclass(slots=True)
class TrieNode:
    children: dict[str, "TrieNode"] = field(default_factory=dict)
    is_word: bool = False
    frequency: int = 0


class AutocompleteTrie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str, frequency: int = 1) -> None:
        if not word:
            raise ValueError("word must not be empty")
        if frequency < 0:
            raise ValueError("frequency must be non-negative")

        node = self.root
        for character in word:
            node = node.children.setdefault(character, TrieNode())

        node.is_word = True
        node.frequency = frequency

    def suggest(self, prefix: str, limit: int = 10) -> list[str]:
        if limit <= 0:
            return []

        node = self.root
        for character in prefix:
            child = node.children.get(character)
            if child is None:
                return []
            node = child

        # A min-heap of (frequency, word) keeps the top k; its root is the weakest.
        heap: list[tuple[int, str]] = []

        def consider(current: TrieNode, suffix: str) -> None:
            if not current.is_word:
                return

            word = prefix + suffix
            item = (current.frequency, word)

            if len(heap) < limit:
                heappush(heap, item)
            elif item > heap[0]:
                heapreplace(heap, item)

        consider(node, "")

        # Iterative DFS avoids Python's recursion-depth limit.
        path: list[str] = []
        stack: list[
            tuple[TrieNode, Iterator[tuple[str, TrieNode]], str | None]
        ] = [(node, iter(node.children.items()), None)]

        while stack:
            current, children, entered_character = stack[-1]

            try:
                character, child = next(children)
            except StopIteration:
                stack.pop()
                if entered_character is not None:
                    path.pop()
                continue

            path.append(character)
            consider(child, "".join(path))
            stack.append((child, iter(child.children.items()), character))

        ordered = sorted(heap, key=lambda item: (-item[0], item[1]))
        return [word for _, word in ordered]


def autocomplete(
    words: list[tuple[str, int]], prefix: str, limit: int = 10
) -> list[str]:
    """Return the highest-frequency words matching a prefix."""
    if limit <= 0:
        return []

    trie = AutocompleteTrie()
    for word, frequency in words:
        trie.insert(word, frequency)

    return trie.suggest(prefix, limit)


if __name__ == "__main__":
    words = [
        ("cat", 10),
        ("car", 20),
        ("cart", 30),
        ("dog", 40),
        ("cats", 5),
    ]
    print(autocomplete(words, "ca", 3))  # ['cart', 'car', 'cat']

Production Considerations

  • Ranking signals: Combine corpus frequency with recency, click-through rate, location, language, and user-specific behavior.

  • Prefix limits: Cap prefix length, result count, and traversal work to prevent expensive queries.

  • Normalization: Decide whether matching is case-sensitive and how punctuation, accents, and Unicode are normalized.

  • Index maintenance: Update or remove stale entries when source data changes. Distributed systems may shard the trie by prefix.

  • Fuzzy matching: A basic trie handles exact prefixes; spelling correction may require an n-gram index or bounded edit-distance search.

Common Pitfalls and Edge Cases

  • Empty corpus: The function returns an empty list.

  • Empty prefix: The root’s subtree is searched, producing the highest-ranked words.

  • One-character terms: They work normally because each character is one trie edge.

  • Duplicates: Inserting the same word again replaces its stored frequency.

  • Negative values: Negative frequencies are rejected; strings such as "-42" remain valid terms.

  • No match: A missing prefix edge returns immediately without traversing the rest of the trie.

  • Incorrect ranking: DFS order is not popularity order; ranking must happen after candidate collection.

  • Unnecessary recursion: Deep terms can exceed Python’s default recursion limit, so the iterative implementation is safer.

  • Binary-tree assumptions: A trie node is multiway and normally uses a child map, not only left and right pointers.

  • Not applicable: Sorted input, disconnected graphs, and cycles are unrelated to trie operations.

53

How does Huffman Coding use a binary tree for compression?

Huffman coding is a lossless compression technique that assigns shorter binary codes to more frequent symbols. It represents those assignments with a binary prefix tree, where every internal node has two children and every leaf represents an original symbol.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  1. Count the frequency of each symbol.

  2. Create a leaf for every distinct symbol.

  3. Repeatedly combine the two subtrees with the lowest frequencies.

  4. Label the left edge 0 and the right edge 1.

  5. Read each root-to-leaf path to obtain that symbol’s code.

The resulting codes are prefix-free: no symbol’s code is a prefix of another symbol’s code. The decoder can therefore follow the tree one bit at a time without ambiguity. For a fixed frequency distribution, Huffman coding minimizes the expected encoded length among prefix codes.

The tree is always full, because every merge creates an internal node with exactly two children. It is not necessarily complete, perfect, or balanced; skewed frequencies can produce a deep tree.

Example Walkthrough

For abracadabra:

Symbol Frequency
a 5
b 2
r 2
c 1
d 1

One valid sequence of merges combines c with d, b with r, and then joins the resulting subtrees. One possible assignment is:

  • a → 0

  • c → 100

  • d → 101

  • b → 110

  • r → 111

This encodes the text as 01101110100010101101110.

Complexity

Let L be the input length, k the number of distinct symbols, B the encoded bit count, and S the sum of all codeword lengths.

Operation Best Average Worst
Build tree O(k log k) O(k log k) O(k log k)
Build code table O(k log k) O(S), data-dependent O(k²)
Encode text O(k log k + B) O(S + B) O(k² + B)
Decode bits O(B) O(B) O(B)

Tree construction performs k - 1 priority-queue merges, each costing O(log k). Encoding also constructs the code table; its worst-case O(k²) cost comes from explicit strings in a highly skewed tree. Decoding performs one tree step per bit.

Tree construction uses O(k) auxiliary space. The code table uses O(S) space, up to O(k²) in the worst case, and its traversal stack has O(h) entries, where h counts edges. Encoding additionally uses O(B) output space, while decoding uses O(D) output-buffer space for D decoded symbols and O(1) traversal state. Inputs are not counted.

Code Example

from __future__ import annotations

from collections import Counter
from dataclasses import dataclass
import heapq


@dataclass
class TreeNode:
    val: str | None
    left: TreeNode | None = None
    right: TreeNode | None = None


def build_huffman_tree(text: str) -> TreeNode | None:
    """Build a Huffman tree from the symbols in text."""
    if not text:
        return None

    frequencies = Counter(text)
    heap: list[tuple[int, int, TreeNode]] = []

    # The serial number breaks frequency ties without comparing nodes.
    for serial, (symbol, frequency) in enumerate(frequencies.items()):
        heapq.heappush(heap, (frequency, serial, TreeNode(symbol)))

    next_serial = len(heap)

    while len(heap) > 1:
        left_frequency, _, left_node = heapq.heappop(heap)
        right_frequency, _, right_node = heapq.heappop(heap)

        parent = TreeNode(
            val=None,
            left=left_node,
            right=right_node,
        )
        heapq.heappush(
            heap,
            (left_frequency + right_frequency, next_serial, parent),
        )
        next_serial += 1

    return heap[0][2]


def build_huffman_codes(root: TreeNode | None) -> dict[str, str]:
    """Return the binary code for every symbol in the tree."""
    if root is None:
        return {}

    codes: dict[str, str] = {}
    stack: list[tuple[TreeNode, str]] = [(root, "")]

    while stack:
        node, prefix = stack.pop()

        if node.val is not None:
            # A one-symbol alphabet assigns one bit per occurrence.
            codes[node.val] = prefix or "0"
            continue

        if node.left is not None:
            stack.append((node.left, prefix + "0"))
        if node.right is not None:
            stack.append((node.right, prefix + "1"))

    return codes


def huffman_encode(text: str, root: TreeNode | None) -> str:
    """Encode text using the codes represented by root."""
    if not text:
        return ""
    if root is None:
        raise ValueError("A tree is required for nonempty text")

    codes = build_huffman_codes(root)
    return "".join(codes[symbol] for symbol in text)


def huffman_decode(bits: str, root: TreeNode | None) -> str:
    """Decode a binary string using the tree represented by root."""
    if root is None:
        if bits:
            raise ValueError("A tree is required for nonempty input")
        return ""

    if root.val is not None:
        if any(bit != "0" for bit in bits):
            raise ValueError("Invalid encoding for a one-symbol tree")
        return root.val * len(bits)

    if not bits:
        raise ValueError("Invalid bit sequence: incomplete code")

    decoded: list[str] = []
    current = root

    for bit in bits:
        if bit not in {"0", "1"}:
            raise ValueError("Encoding must contain only 0 and 1")
        if current.val is not None:
            raise ValueError("Invalid bit sequence: extra bits")

        current = current.left if bit == "0" else current.right
        if current is None:
            raise ValueError("Invalid bit sequence: no such tree path")

    if current.val is None:
        raise ValueError("Invalid bit sequence: incomplete code")

    decoded.append(current.val)
    return "".join(decoded)


text = "abracadabra"
root = build_huffman_tree(text)
encoded = huffman_encode(text, root)

print(encoded)
print(huffman_decode(encoded, root))
# 01101110100010101101110
# abracadabra

Common Pitfalls

  • Empty input: No tree is required, and encoding produces an empty string.

  • One distinct symbol: This example assigns 0 to every occurrence; encoding and decoding must apply that convention consistently.

  • Duplicates: Occurrences are aggregated into one leaf using frequency counts.

  • Negative values: This implementation operates on characters. If numeric values are tokenized first, a negative number is simply another symbol whose frequency is counted.

  • Sorted input: Input order does not matter because only symbol frequencies affect construction.

  • Codebook overhead: The decoder needs the tree or equivalent codebook; transmitting or storing it adds overhead and can make small inputs larger.

  • Graph edge cases: Disconnected graphs and cycles do not apply to a Huffman prefix tree.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 53 Binary Tree answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects