Count Complete Tree Nodes

🎯

Count Complete Tree Nodes

easyTREEAmazonGoogle

Imagine you have a nearly full family tree and want to quickly count how many members are in it without visiting every single person.

💡 This problem asks you to count nodes in a special kind of binary tree called a complete tree. Beginners often struggle because a naive traversal is simple but inefficient, and understanding how to leverage the tree's completeness property for faster counting requires deeper insight.

📋

Problem Statement

Given the root of a complete binary tree, return the number of the nodes in the tree. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

The number of nodes in the tree is in the range [0, 10^5].The tree is guaranteed to be complete.

💡

Example

Input"root = [1,2,3,4,5,6]"

Output6

The tree has nodes 1 through 6 arranged as a complete binary tree, so the count is 6.

Input"root = []"

Output0

An empty tree has zero nodes.

• Empty tree → 0
• Tree with only root node → 1
• Complete tree with last level half filled → correct count
• Complete tree with only one child at last level → correct count

⚠️

Common Mistakes

Not handling empty tree (null root)

Code throws null pointer exception or returns wrong count

✅ Add base case to return 0 if root is null

Assuming left and right subtree heights always equal

Incorrect node count for incomplete last level

✅ Check heights and recurse when they differ

Incorrect bit manipulation or index calculation in binary search approach

Existence check fails, leading to wrong counts

✅ Carefully implement binary search and node traversal according to bits

Using BFS or iterative traversal without leveraging completeness

Solution is correct but inefficient (O(n))

✅ Use height checks or binary search to optimize

Stack overflow due to deep recursion on large trees

Runtime error on large inputs

✅ Use iterative approach or optimized recursion with height checks

🧠

Brute Force (Simple DFS Traversal)

💡 This approach exists because it is the most straightforward way to count nodes by visiting each node exactly once. It helps beginners understand the problem and tree traversal basics before optimizing.

Intuition

Traverse the entire tree using DFS and count every node encountered. Since the tree is complete, this will count all nodes but does not leverage the completeness property for speed.

Algorithm

1. Start at the root node.
2. Recursively count nodes in the left subtree.
3. Recursively count nodes in the right subtree.
4. Sum counts from left and right subtrees and add 1 for the current node.

💡 The recursion is simple but can be inefficient for large trees because it visits every node.

</>

Code

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

def countNodes(root):
    if not root:
        return 0
    left_count = countNodes(root.left)
    right_count = countNodes(root.right)
    return 1 + left_count + right_count

# Example usage:
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), None))
    print(countNodes(root))  # Output: 6

Line Notes

def countNodes(root):Defines the main function to count nodes starting from root

if not root:Base case: if node is None, count is zero

left_count = countNodes(root.left)Recursively count nodes in left subtree

right_count = countNodes(root.right)Recursively count nodes in right subtree

return 1 + left_count + right_countSum counts of left and right subtrees plus current node

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftCount = countNodes(root.left);
        int rightCount = countNodes(root.right);
        return 1 + leftCount + rightCount;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        Solution sol = new Solution();
        System.out.println(sol.countNodes(root)); // Output: 6
    }
}

Line Notes

public int countNodes(TreeNode root)Main method to count nodes recursively

if (root == null) return 0;Base case: no node means count zero

int leftCount = countNodes(root.left);Count nodes in left subtree recursively

int rightCount = countNodes(root.right);Count nodes in right subtree recursively

return 1 + leftCount + rightCount;Sum counts plus current node

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int countNodes(TreeNode* root) {
    if (!root) return 0;
    int leftCount = countNodes(root->left);
    int rightCount = countNodes(root->right);
    return 1 + leftCount + rightCount;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    cout << countNodes(root) << endl; // Output: 6
    return 0;
}

Line Notes

int countNodes(TreeNode* root)Function to count nodes recursively

if (!root) return 0;Base case: null node means zero count

int leftCount = countNodes(root->left);Count nodes in left subtree

int rightCount = countNodes(root->right);Count nodes in right subtree

return 1 + leftCount + rightCount;Sum counts plus current node

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function countNodes(root) {
    if (root === null) return 0;
    const leftCount = countNodes(root.left);
    const rightCount = countNodes(root.right);
    return 1 + leftCount + rightCount;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3, new TreeNode(6), null)
);
console.log(countNodes(root)); // Output: 6

Line Notes

function countNodes(root)Defines recursive function to count nodes

if (root === null) return 0;Base case: no node means zero count

const leftCount = countNodes(root.left);Recursively count left subtree nodes

const rightCount = countNodes(root.right);Recursively count right subtree nodes

return 1 + leftCount + rightCount;Sum counts plus current node

⏱

Complexity

TimeO(n)

SpaceO(h) where h is tree height due to recursion stack

We visit every node once, so time is linear in number of nodes. Space is proportional to tree height due to recursion.

💡 For n=100,000 nodes, this means about 100,000 operations and recursion depth up to about 17 (log2(100,000))

Interview Verdict: Accepted but not optimal

This approach works but is slow for very large trees. It is a good starting point to understand the problem before optimizing.

🧠

Better (Use Tree Height to Check Perfect Subtrees)

💡 This approach exists to leverage the complete tree property to avoid visiting every node, improving efficiency by checking subtree heights.

Intuition

If the left and right subtree heights are equal, the left subtree is a perfect binary tree and its node count can be computed directly. Otherwise, recurse on the subtrees accordingly.

Algorithm

1. Compute left subtree height by traversing left children.
2. Compute right subtree height by traversing right children.
3. If heights are equal, left subtree is perfect; count nodes directly.
4. Otherwise, recursively count nodes in left and right subtrees and sum.

💡 This reduces work by avoiding full traversal of perfect subtrees, but still uses recursion.

</>

Code

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

def height_left(node):
    h = 0
    while node:
        h += 1
        node = node.left
    return h

def height_right(node):
    h = 0
    while node:
        h += 1
        node = node.right
    return h

def countNodes(root):
    if not root:
        return 0
    left_h = height_left(root)
    right_h = height_right(root)
    if left_h == right_h:
        return (2 ** left_h) - 1
    else:
        return 1 + countNodes(root.left) + countNodes(root.right)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), None))
    print(countNodes(root))  # Output: 6

Line Notes

def height_left(node):Helper to compute height by going left

while node:Traverse down left children to measure height

if left_h == right_h:If heights equal, subtree is perfect

return (2 ** left_h) - 1Calculate nodes in perfect subtree directly

return 1 + countNodes(root.left) + countNodes(root.right)Otherwise recurse on subtrees

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int heightLeft(TreeNode node) {
        int h = 0;
        while (node != null) {
            h++;
            node = node.left;
        }
        return h;
    }

    private int heightRight(TreeNode node) {
        int h = 0;
        while (node != null) {
            h++;
            node = node.right;
        }
        return h;
    }

    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftH = heightLeft(root);
        int rightH = heightRight(root);
        if (leftH == rightH) {
            return (1 << leftH) - 1;
        } else {
            return 1 + countNodes(root.left) + countNodes(root.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        Solution sol = new Solution();
        System.out.println(sol.countNodes(root)); // Output: 6
    }
}

Line Notes

private int heightLeft(TreeNode node)Compute height by traversing left children

while (node != null)Loop down left subtree to measure height

if (leftH == rightH)Check if subtree is perfect

return (1 << leftH) - 1;Calculate nodes in perfect subtree using bit shift

return 1 + countNodes(root.left) + countNodes(root.right);Recurse if subtree not perfect

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int heightLeft(TreeNode* node) {
    int h = 0;
    while (node) {
        h++;
        node = node->left;
    }
    return h;
}

int heightRight(TreeNode* node) {
    int h = 0;
    while (node) {
        h++;
        node = node->right;
    }
    return h;
}

int countNodes(TreeNode* root) {
    if (!root) return 0;
    int leftH = heightLeft(root);
    int rightH = heightRight(root);
    if (leftH == rightH) {
        return (1 << leftH) - 1;
    } else {
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    cout << countNodes(root) << endl; // Output: 6
    return 0;
}

Line Notes

int heightLeft(TreeNode* node)Calculate height by traversing left children

while (node)Loop down left subtree to measure height

if (leftH == rightH)Check if subtree is perfect

return (1 << leftH) - 1;Calculate perfect subtree node count using bit shift

return 1 + countNodes(root->left) + countNodes(root->right);Recurse if subtree not perfect

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function heightLeft(node) {
    let h = 0;
    while (node) {
        h++;
        node = node.left;
    }
    return h;
}

function heightRight(node) {
    let h = 0;
    while (node) {
        h++;
        node = node.right;
    }
    return h;
}

function countNodes(root) {
    if (root === null) return 0;
    const leftH = heightLeft(root);
    const rightH = heightRight(root);
    if (leftH === rightH) {
        return (1 << leftH) - 1;
    } else {
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3, new TreeNode(6), null)
);
console.log(countNodes(root)); // Output: 6

Line Notes

function heightLeft(node)Helper to compute height by going left

while (node)Traverse left children to measure height

if (leftH === rightH)Check if subtree is perfect

return (1 << leftH) - 1;Calculate nodes in perfect subtree using bit shift

return 1 + countNodes(root.left) + countNodes(root.right);Recurse if subtree not perfect

⏱

Complexity

TimeO((log n)^2)

SpaceO(log n) due to recursion stack

Each recursive call computes subtree heights in O(log n), and there are O(log n) calls, so total time is O((log n)^2).

💡 For n=100,000 nodes, this means about 289 operations (17*17), much faster than brute force.

Interview Verdict: Accepted and efficient for large trees

This approach is optimal for complete trees and is the preferred solution in interviews.

🧠

Optimal (Iterative Binary Search on Last Level)

💡 This approach uses binary search on the last level to count nodes without recursion, further optimizing performance and avoiding stack overhead.

Intuition

Since the tree is complete, the last level nodes are filled from left to right. We can binary search the index of the last node on the last level by checking node existence.

Algorithm

1. Compute tree height by traversing left children.
2. If height is 0, return 0.
3. Use binary search on the range [0, 2^(height-1) - 1] to find the last existing node index on the last level.
4. Check node existence by traversing from root using bits of the index.
5. Return total nodes as nodes above last level plus last level count.

💡 This approach avoids recursion and uses binary search to minimize node visits.

</>

Code

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

def height(root):
    h = 0
    while root:
        h += 1
        root = root.left
    return h

def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1
    for _ in range(h - 1):
        mid = (left + right) // 2
        if idx <= mid:
            root = root.left
            right = mid
        else:
            root = root.right
            left = mid + 1
    return root is not None

def countNodes(root):
    if not root:
        return 0
    h = height(root)
    if h == 1:
        return 1
    left, right = 0, 2**(h - 1) - 1
    while left <= right:
        mid = (left + right) // 2
        if exists(mid, h, root):
            left = mid + 1
        else:
            right = mid - 1
    return (2**(h - 1) - 1) + left

# Example usage:
if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), None))
    print(countNodes(root))  # Output: 6

Line Notes

def height(root):Compute tree height by going left

while root:Traverse left children to measure height

def exists(idx, h, root):Check if node at index idx exists on last level

for _ in range(h - 1):Traverse tree according to bits of idx to decide path

if idx <= mid:If idx is in left half, go left subtree and update right boundary

else:If node does not exist, search left half

return root is not NoneReturn True if node exists at this path, else False

while left <= right:Binary search over last level indices to find last existing node

if exists(mid, h, root):If node exists at mid, search right half to find last node

return (2**(h - 1) - 1) + leftReturn total nodes: full levels plus count of last level nodes

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int height(TreeNode root) {
        int h = 0;
        while (root != null) {
            h++;
            root = root.left;
        }
        return h;
    }

    private boolean exists(int idx, int h, TreeNode root) {
        int left = 0, right = (1 << (h - 1)) - 1;
        for (int i = 0; i < h - 1; i++) {
            int mid = (left + right) / 2;
            if (idx <= mid) {
                root = root.left;
                right = mid;
            } else {
                root = root.right;
                left = mid + 1;
            }
        }
        return root != null;
    }

    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int h = height(root);
        if (h == 1) return 1;
        int left = 0, right = (1 << (h - 1)) - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (exists(mid, h, root)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (1 << (h - 1)) - 1 + left;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        Solution sol = new Solution();
        System.out.println(sol.countNodes(root)); // Output: 6
    }
}

Line Notes

private int height(TreeNode root)Compute tree height by traversing left children

while (root != null)Loop down left subtree to measure height

private boolean exists(int idx, int h, TreeNode root)Check if node exists at index idx on last level

for (int i = 0; i < h - 1; i++)Traverse tree according to bits of idx to decide path

if (idx <= mid)If idx in left half, go left subtree and update right boundary

elseIf node does not exist, search left half

return root != null;Return true if node exists at this path

while (left <= right)Binary search over last level indices to find last existing node

if (exists(mid, h, root))If node exists at mid, search right half

return (1 << (h - 1)) - 1 + left;Return total nodes: full levels plus last level count

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int height(TreeNode* root) {
    int h = 0;
    while (root) {
        h++;
        root = root->left;
    }
    return h;
}

bool exists(int idx, int h, TreeNode* root) {
    int left = 0, right = (1 << (h - 1)) - 1;
    for (int i = 0; i < h - 1; i++) {
        int mid = (left + right) / 2;
        if (idx <= mid) {
            root = root->left;
            right = mid;
        } else {
            root = root->right;
            left = mid + 1;
        }
    }
    return root != nullptr;
}

int countNodes(TreeNode* root) {
    if (!root) return 0;
    int h = height(root);
    if (h == 1) return 1;
    int left = 0, right = (1 << (h - 1)) - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (exists(mid, h, root)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return (1 << (h - 1)) - 1 + left;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    cout << countNodes(root) << endl; // Output: 6
    return 0;
}

Line Notes

int height(TreeNode* root)Compute tree height by traversing left children

while (root)Loop down left subtree to measure height

bool exists(int idx, int h, TreeNode* root)Check if node exists at index idx on last level

for (int i = 0; i < h - 1; i++)Traverse tree according to bits of idx to decide path

if (idx <= mid)If idx in left half, go left subtree and update right boundary

elseIf node does not exist, search left half

return root != nullptr;Return true if node exists at this path

while (left <= right)Binary search over last level indices to find last existing node

if (exists(mid, h, root))If node exists at mid, search right half

return (1 << (h - 1)) - 1 + left;Return total nodes: full levels plus last level count

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function height(root) {
    let h = 0;
    while (root) {
        h++;
        root = root.left;
    }
    return h;
}

function exists(idx, h, root) {
    let left = 0, right = (1 << (h - 1)) - 1;
    for (let i = 0; i < h - 1; i++) {
        let mid = Math.floor((left + right) / 2);
        if (idx <= mid) {
            root = root.left;
            right = mid;
        } else {
            root = root.right;
            left = mid + 1;
        }
    }
    return root !== null;
}

function countNodes(root) {
    if (root === null) return 0;
    const h = height(root);
    if (h === 1) return 1;
    let left = 0, right = (1 << (h - 1)) - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (exists(mid, h, root)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return (1 << (h - 1)) - 1 + left;
}

// Example usage:
const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), new TreeNode(5)),
    new TreeNode(3, new TreeNode(6), null)
);
console.log(countNodes(root)); // Output: 6

Line Notes

function height(root)Compute tree height by traversing left children

while (root)Loop down left subtree to measure height

function exists(idx, h, root)Check if node exists at index idx on last level

for (let i = 0; i < h - 1; i++)Traverse tree according to bits of idx to decide path

if (idx <= mid)If idx in left half, go left subtree and update right boundary

elseIf node does not exist, search left half

return root !== null;Return true if node exists at this path

while (left <= right)Binary search over last level indices to find last existing node

if (exists(mid, h, root))If node exists at mid, search right half

return (1 << (h - 1)) - 1 + left;Return total nodes: full levels plus last level count

⏱

Complexity

TimeO((log n)^2)

SpaceO(1)

Binary search on last level indices takes O(log n), each existence check takes O(log n), total O((log n)^2).

💡 For n=100,000 nodes, this means about 289 operations, very efficient and avoids recursion stack overhead.

Interview Verdict: Accepted and optimal iterative solution

This approach is the most efficient and avoids recursion, ideal for interviews if comfortable with binary search on trees.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (height check recursion) is the best balance of simplicity and efficiency to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(h) recursion stack	Yes (deep recursion)	N/A	Mention only - never code unless asked for baseline
2. Height Check Recursion	O((log n)^2)	O(log n) recursion stack	Low	N/A	Preferred approach to code in interviews
3. Iterative Binary Search on Last Level	O((log n)^2)	O(1)	No	N/A	Use if comfortable with binary search and iterative tree traversal

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm the tree is complete.Step 2: Present the brute force DFS solution to show correctness.Step 3: Explain the optimization using subtree heights to count perfect subtrees.Step 4: Optionally, discuss the binary search approach on the last level for optimal performance.Step 5: Code the chosen approach and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of tree properties, recursion, optimization using completeness, and ability to implement efficient code.

Common Follow-ups

• What if the tree is not complete? → Use simple DFS counting.
• Can you do this iteratively? → Yes, use BFS or the binary search approach.
• What is the time complexity of your solution? → Explain O(n) for brute force, O((log n)^2) for optimized.
• How does the complete tree property help? → It allows counting perfect subtrees without full traversal.

💡 These follow-ups test your depth of understanding and ability to adapt solutions to variations.

🔍

Pattern Recognition

When to Use

1) Tree is complete or perfect binary tree, 2) Need to count nodes efficiently, 3) Problem hints at leveraging tree height or completeness, 4) Avoid full traversal if possible.

Signature Phrases

complete binary treecount the number of nodesall levels except last are fullnodes as far left as possible

NOT This Pattern When

General tree traversal or binary search tree problems without completeness property

Similar Problems

Count Nodes in a Binary Tree - simpler version without completenessCount Nodes in a Perfect Binary Tree - uses direct formulaCount Nodes in a Full Binary Tree - related counting problem

Practice

1. Given the following Morris inorder traversal code, what is the final output list after running inorderTraversal on this tree?

Tree structure:
2
/ \ 1 3

from typing import Optional, List

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

def inorderTraversal(root: Optional[TreeNode]) -> List[int]:
    result = []
    current = root
    while current:
        if not current.left:
            result.append(current.val)  # visit node
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if not predecessor.right:
                predecessor.right = current  # create thread
                current = current.left
            else:
                predecessor.right = None  # remove thread
                result.append(current.val)  # visit node
                current = current.right
    return result

easy

A. [1, 2, 3]

B. [1, 3, 2]

C. [2, 1, 3]

D. [3, 2, 1]

Solution

1. Step 1: Trace traversal starting at root=2

   Current=2 has left child 1, find predecessor in left subtree: node 1 (no right child). Create thread from 1.right to 2, move current to 1.

2. Step 2: Visit node 1 (no left child), append 1, move current to 1.right which points to 2 (thread).

   Remove thread, append 2, move current to 2.right=3. Node 3 has no left child, append 3, move current to null.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inorder traversal of tree 1,2,3 is [1,2,3] [OK]

Hint: Inorder traversal visits left, root, right [OK]

Common Mistakes:

• Appending before removing thread
• Visiting root before left subtree
• Confusing preorder with inorder output

2. Given the following iterative postorder traversal code, what is the final output when run on the tree: root = TreeNode(1, None, TreeNode(2, TreeNode(3)))?

def postorderTraversal(root):
    result = []
    stack = []
    last_visited = None
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        peek_node = stack[-1]
        if peek_node.right and last_visited != peek_node.right:
            current = peek_node.right
        else:
            result.append(peek_node.val)
            last_visited = stack.pop()
    return result

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 2, 1]

D. [3, 1, 2]

Solution

1. Step 1: Trace traversal on given tree

   Start at root(1), go left (None), push 1. Then peek 1, right child is 2, move to 2, push 2, go left to 3, push 3, left None.

2. Step 2: Process nodes in postorder

   3 has no children, append 3. Back to 2, right visited, append 2. Back to 1, right visited, append 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches postorder [3, 2, 1] [OK]

Hint: Postorder output for this tree is [3,2,1] [OK]

Common Mistakes:

• Confusing order of appending nodes
• Off-by-one in stack popping

3. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?

easy

A. Use a greedy approach by always attaching nodes as left children when possible.

B. Use dynamic programming to store subtrees and avoid recomputation.

C. Use recursion with a hash map to quickly find root indices in the inorder array.

D. Use breadth-first search to reconstruct the tree level by level.

Solution

1. Step 1: Understand the problem constraints

   Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.

2. Step 2: Evaluate approaches

   Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map lookup avoids O(n) search per recursion [OK]

Hint: Hash map lookup avoids repeated linear searches [OK]

Common Mistakes:

• Assuming greedy or BFS can reconstruct tree uniquely
• Confusing DP with tree construction
• Ignoring index lookup cost

4. Identify the bug in the following Morris preorder traversal code snippet that causes the tree structure to remain modified after traversal:

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                # Bug here
                current = current.right
    return result

medium

A. Line resetting predecessor.right to None is missing in the else block

B. Appending current.val before moving to left child is incorrect

C. The inner while loop condition should check predecessor.left instead of predecessor.right

D. The check for current.left being None should be after the else block

Solution

1. Step 1: Identify missing restoration of tree structure

   In Morris traversal, after visiting left subtree, predecessor.right must be reset to None to restore original tree.

2. Step 2: Locate missing line

   The else block lacks the line predecessor.right = None, causing the threaded link to persist.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without resetting, tree remains modified after traversal [OK]

Hint: Always reset threaded links to None after use [OK]

Common Mistakes:

• Forgetting to restore tree structure
• Appending nodes in wrong order
• Incorrect loop conditions

5. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and node values can be negative. Which of the following approaches correctly adapts the maximum path sum algorithm to handle this variant?

hard

A. Use the same postorder traversal with global max tracking, ignoring negative gains as before.

B. Detect cycles and use dynamic programming with memoization to avoid infinite loops, allowing repeated nodes in paths.

C. Convert the tree to a graph and run Bellman-Ford algorithm to find the maximum sum path allowing cycles.

D. Use depth-first search with pruning to explore all paths, but limit path length to avoid infinite loops.

Solution

1. Step 1: Understand the impact of allowing node reuse

   Allowing cycles means paths can revisit nodes infinitely, so naive DFS or postorder traversal fails due to infinite loops.

2. Step 2: Identify correct approach

   Dynamic programming with cycle detection and memoization prevents infinite recursion and correctly computes max sums with repeated nodes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Memoization with cycle detection handles repeated nodes safely [OK]

Hint: Cycle detection and memoization needed for repeated nodes [OK]

Common Mistakes:

• Using same postorder traversal causes infinite loops
• Bellman-Ford is for shortest paths, not max sums with negative cycles
• DFS without cycle checks leads to infinite recursion