Maximum Depth of Binary Tree

🎯

Maximum Depth of Binary Tree

easyTREEAmazonFacebookGoogle

Imagine you are analyzing the structure of a company's organizational chart represented as a binary tree, and you want to find out how many levels of management exist from the CEO down to the lowest employee.

💡 This problem asks for the maximum depth of a binary tree, which is a fundamental tree property. Beginners often struggle because they don't immediately see how to traverse the tree recursively and combine results from subtrees to get the final answer.

📋

Problem Statement

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

The number of nodes in the tree is in the range [1, 10^5].Node values can be any integer.The tree is not necessarily balanced.

💡

Example

Input"root = [3,9,20,null,null,15,7]"

Output3

The longest path is 3 -> 20 -> 15 or 3 -> 20 -> 7, both have length 3.

• Single node tree → depth is 1
• Tree with only left children → depth equals number of nodes
• Tree with only right children → depth equals number of nodes
• Empty tree (null root) → depth is 0

⚠️

Common Mistakes

Not handling null root (empty tree) case

Code throws null pointer exception or returns incorrect depth

✅ Add base case to return 0 if root is null

Returning sum of left and right depths instead of max

Incorrect depth calculation, overestimates depth

✅ Use max(left_depth, right_depth) instead of left_depth + right_depth

Not incrementing depth by 1 at current node

Depth is off by one, usually too small

✅ Add 1 to max depth of children before returning

Using BFS but not incrementing depth after each level

Depth remains zero or incorrect

✅ Increment depth counter after processing all nodes at a level

Confusing depth with height or number of edges

Off-by-one errors in output

✅ Clarify definition: depth counts nodes along path, including root and leaf

🧠

Brute Force (Pure Recursion)

💡 Starting with pure recursion helps understand the problem from first principles by exploring every path fully without optimization.

Intuition

The maximum depth of a tree is 1 plus the maximum depth of its left and right subtrees. We recursively compute depths of subtrees and combine them.

Algorithm

1. If the current node is null, return 0 as depth.
2. Recursively find the maximum depth of the left subtree.
3. Recursively find the maximum depth of the right subtree.
4. Return 1 plus the maximum of the left and right subtree depths.

💡 The recursion naturally breaks the problem into smaller subproblems, but beginners may find it tricky to combine results correctly.

</>

Code

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

def maxDepth(root):
    if root is None:
        return 0
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    return 1 + max(left_depth, right_depth)

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxDepth(root))  # Output: 3

Line Notes

if root is None:Base case: if node is null, depth is zero because no nodes exist here

left_depth = maxDepth(root.left)Recursively compute depth of left subtree

right_depth = maxDepth(root.right)Recursively compute depth of right subtree

return 1 + max(left_depth, right_depth)Add 1 for current node and take max depth from children

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.maxDepth(root)); // Output: 3
    }
}

Line Notes

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

int leftDepth = maxDepth(root.left);Recursively find left subtree depth

int rightDepth = maxDepth(root.right);Recursively find right subtree depth

return 1 + Math.max(leftDepth, rightDepth);Add current node and pick max depth

#include <iostream>
#include <algorithm>
using namespace std;

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

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return 1 + max(leftDepth, rightDepth);
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << maxDepth(root) << endl; // Output: 3
    return 0;
}

Line Notes

if (root == nullptr) return 0;Base case: empty node means depth zero

int leftDepth = maxDepth(root->left);Recursively compute left subtree depth

int rightDepth = maxDepth(root->right);Recursively compute right subtree depth

return 1 + max(leftDepth, rightDepth);Add current node and choose max depth

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

function maxDepth(root) {
    if (root === null) return 0;
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    return 1 + Math.max(leftDepth, rightDepth);
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxDepth(root)); // Output: 3

Line Notes

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

const leftDepth = maxDepth(root.left);Recursively find left subtree depth

const rightDepth = maxDepth(root.right);Recursively find right subtree depth

return 1 + Math.max(leftDepth, rightDepth);Add current node and pick max depth

⏱

Complexity

TimeO(n)

SpaceO(h)

We visit each node once, so time is O(n). The recursion stack can go as deep as the height h of the tree, so space is O(h).

💡 For a tree with 1000 nodes, this means roughly 1000 operations and stack depth up to the height, which is efficient for typical interview constraints.

Interview Verdict: Accepted

This approach is efficient and accepted for this problem, making it a solid baseline solution.

🧠

Iterative DFS Using Stack

💡 This approach replaces recursion with an explicit stack to simulate DFS, helping avoid recursion stack overflow and demonstrating iterative tree traversal.

Intuition

Use a stack to traverse nodes depth-first, tracking the depth of each node explicitly, and update the maximum depth encountered.

Algorithm

1. Initialize a stack with the root node and its depth as 1.
2. While the stack is not empty, pop a node and its depth.
3. Update the maximum depth if current depth is greater.
4. Push the node's children onto the stack with depth + 1.

💡 Tracking depth explicitly is key here, which can be tricky for beginners used to recursion.

</>

Code

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

def maxDepth(root):
    if root is None:
        return 0
    stack = [(root, 1)]
    max_depth = 0
    while stack:
        node, depth = stack.pop()
        if node:
            max_depth = max(max_depth, depth)
            stack.append((node.left, depth + 1))
            stack.append((node.right, depth + 1))
    return max_depth

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxDepth(root))  # Output: 3

Line Notes

if root is None:Handle empty tree edge case

stack = [(root, 1)]Initialize stack with root node and depth 1

node, depth = stack.pop()Pop current node and its depth for processing

max_depth = max(max_depth, depth)Update max depth if current depth is larger

import java.util.Stack;

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
        stack.push(new Pair<>(root, 1));
        int maxDepth = 0;
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> current = stack.pop();
            TreeNode node = current.getKey();
            int depth = current.getValue();
            if (node != null) {
                maxDepth = Math.max(maxDepth, depth);
                stack.push(new Pair<>(node.left, depth + 1));
                stack.push(new Pair<>(node.right, depth + 1));
            }
        }
        return maxDepth;
    }

    // Simple Pair class since Java 8+ doesn't have built-in Pair
    public static class Pair<K,V> {
        private K key;
        private V value;
        public Pair(K key, V value) { this.key = key; this.value = value; }
        public K getKey() { return key; }
        public V getValue() { return value; }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.maxDepth(root)); // Output: 3
    }
}

Line Notes

if (root == null) return 0;Handle empty tree

Stack<Pair<TreeNode, Integer>> stack = new Stack<>();Initialize stack to hold nodes with their depths

Pair<TreeNode, Integer> current = stack.pop();Pop node and depth for processing

maxDepth = Math.max(maxDepth, depth);Update max depth if current depth is greater

#include <iostream>
#include <stack>
#include <utility>
using namespace std;

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

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    stack<pair<TreeNode*, int>> stk;
    stk.push({root, 1});
    int max_depth = 0;
    while (!stk.empty()) {
        auto [node, depth] = stk.top();
        stk.pop();
        if (node) {
            max_depth = max(max_depth, depth);
            stk.push({node->left, depth + 1});
            stk.push({node->right, depth + 1});
        }
    }
    return max_depth;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << maxDepth(root) << endl; // Output: 3
    return 0;
}

Line Notes

if (root == nullptr) return 0;Handle empty tree case

stack<pair<TreeNode*, int>> stk;Stack stores nodes paired with their depth

auto [node, depth] = stk.top();Unpack node and depth from stack top

max_depth = max(max_depth, depth);Update max depth if current depth is larger

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

function maxDepth(root) {
    if (root === null) return 0;
    const stack = [[root, 1]];
    let maxDepth = 0;
    while (stack.length > 0) {
        const [node, depth] = stack.pop();
        if (node !== null) {
            maxDepth = Math.max(maxDepth, depth);
            stack.push([node.left, depth + 1]);
            stack.push([node.right, depth + 1]);
        }
    }
    return maxDepth;
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxDepth(root)); // Output: 3

Line Notes

if (root === null) return 0;Handle empty tree

const stack = [[root, 1]];Initialize stack with root and depth 1

const [node, depth] = stack.pop();Pop node and depth for processing

maxDepth = Math.max(maxDepth, depth);Update max depth if current depth is greater

⏱

Complexity

TimeO(n)

SpaceO(h)

Each node is visited once, so time is O(n). The stack can hold up to the height h of the tree, so space is O(h).

💡 This approach avoids recursion but uses similar memory proportional to tree height.

Interview Verdict: Accepted

This iterative approach is equally efficient and useful when recursion depth is a concern.

🧠

Breadth-First Search (Level Order Traversal)

💡 Using BFS to find maximum depth is intuitive because depth corresponds to the number of levels in the tree.

Intuition

Traverse the tree level by level using a queue, incrementing depth after processing each level until all nodes are visited.

Algorithm

1. If the root is null, return 0.
2. Initialize a queue and enqueue the root.
3. While the queue is not empty, process all nodes at the current level.
4. Increment depth after processing each level.
5. Return the depth after all levels are processed.

💡 The key is to process nodes level by level, which naturally counts the depth.

</>

Code

from collections import deque

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

def maxDepth(root):
    if root is None:
        return 0
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

# Example usage:
if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(maxDepth(root))  # Output: 3

Line Notes

if root is None:Handle empty tree edge case

queue = deque([root])Initialize queue with root node

for _ in range(level_size):Process all nodes at current level

depth += 1Increment depth after finishing current level

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }
        return depth;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sol.maxDepth(root)); // Output: 3
    }
}

Line Notes

if (root == null) return 0;Handle empty tree

Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS

for (int i = 0; i < levelSize; i++) {Process all nodes at current level

depth++;Increment depth after processing a level

#include <iostream>
#include <queue>
using namespace std;

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

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        depth++;
    }
    return depth;
}

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    cout << maxDepth(root) << endl; // Output: 3
    return 0;
}

Line Notes

if (root == nullptr) return 0;Handle empty tree

queue<TreeNode*> q;Initialize queue for BFS

for (int i = 0; i < levelSize; i++) {Process all nodes at current level

depth++;Increment depth after processing a level

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

function maxDepth(root) {
    if (root === null) return 0;
    const queue = [root];
    let depth = 0;
    while (queue.length > 0) {
        let levelSize = queue.length;
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        depth++;
    }
    return depth;
}

// Example usage:
const root = new TreeNode(3,
    new TreeNode(9),
    new TreeNode(20, new TreeNode(15), new TreeNode(7))
);
console.log(maxDepth(root)); // Output: 3

Line Notes

if (root === null) return 0;Handle empty tree

const queue = [root];Initialize queue with root node

for (let i = 0; i < levelSize; i++) {Process all nodes at current level

depth++;Increment depth after processing a level

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, so time is O(n). The queue can hold up to the maximum number of nodes at any level, which can be O(n) in worst case.

💡 For a balanced tree with 1000 nodes, the max width is about 500, so space is manageable.

Interview Verdict: Accepted

BFS is a good alternative to DFS and is especially intuitive for level-based problems.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, the recursive DFS approach is simplest and fastest to implement. Iterative DFS and BFS are useful alternatives if recursion depth is a concern.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Pure Recursion)	O(n)	O(h) recursion stack	Yes (deep recursion)	N/A	Mention and code in most interviews
2. Iterative DFS Using Stack	O(n)	O(h) stack	No	N/A	Good alternative if recursion is risky
3. BFS Level Order Traversal	O(n)	O(n) queue	No	N/A	Good for level-based problems or when BFS is preferred

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, followed by iterative and BFS methods. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and ask about empty tree cases.Step 2: Describe the brute force recursive approach and its base case.Step 3: Discuss iterative DFS to avoid recursion stack issues.Step 4: Present BFS as an alternative that counts levels directly.Step 5: Code your 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 traversal, recursion base cases, and ability to handle edge cases like empty or skewed trees.

Common Follow-ups

• What if the tree is very deep? → Use iterative DFS to avoid stack overflow.
• How to find minimum depth? → Modify BFS to return depth at first leaf node.

💡 These follow-ups test your adaptability and understanding of related tree depth concepts.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree traversal, 2) Need to measure a property from root to leaves, 3) Keywords like 'maximum depth' or 'height', 4) Requires combining results from subtrees.

Signature Phrases

maximum depthlongest path from root to leafheight of binary tree

NOT This Pattern When

Problems asking for path sums or subtree sums are different patterns involving value aggregation.

Similar Problems

Diameter of Binary Tree - measures longest path between any two nodesBalanced Binary Tree - checks height difference between subtreesMinimum Depth of Binary Tree - finds shortest path to leaf

Practice

1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?

easy

A. Postorder traversal using two stacks

B. Level-order traversal using a queue

C. Morris preorder traversal using threaded binary tree

D. Inorder traversal using recursion

Solution

1. Step 1: Understand traversal order requirement

   The problem requires visiting root before left and right subtrees, which is preorder traversal.

2. Step 2: Identify approach with no extra space

   Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Preorder visits root first; Morris traversal achieves this with O(1) space [OK]

Hint: Preorder visits root before children [OK]

Common Mistakes:

• Confusing inorder or postorder with preorder traversal
• Assuming recursion is always needed
• Using level-order which visits nodes by depth

2. Consider the following iterative DFS code snippet for counting paths with sum equal to targetSum in a binary tree. Given the tree with root value 1, left child 2, right child 3, and targetSum = 3, what is the final value of result after the loop finishes?

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0
        prefix_counts = {0: 1}
        result = 0
        stack = [(root, 0, False)]  # node, current_sum, visited_children

        while stack:
            node, current_sum, visited = stack.pop()
            if node is None:
                continue
            if not visited:
                current_sum += node.val
                result += prefix_counts.get(current_sum - targetSum, 0)
                prefix_counts[current_sum] = prefix_counts.get(current_sum, 0) + 1
                stack.append((node, current_sum, True))  # Mark node as visited
                stack.append((node.right, current_sum, False))
                stack.append((node.left, current_sum, False))
            else:
                prefix_counts[current_sum] -= 1

        return result

easy

A. 1

B. 0

C. 3

D. 2

Solution

1. Step 1: Trace initial stack and prefix_counts

   Start with stack=[(1,0,False)], prefix_counts={0:1}, result=0.

2. Step 2: Process nodes and update result

   Paths summing to 3 are: (1->2) and (3) alone, total 2 paths counted.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two valid paths found matching target sum [OK]

Hint: Count paths by prefix sums during DFS traversal [OK]

Common Mistakes:

• Missing the single node path (3)
• Double counting paths due to prefix_counts not decremented
• Off-by-one in updating result

3. Given the following code snippet for checking if a binary tree is symmetric, what is the final return value when called with the tree root = TreeNode(1, TreeNode(2), TreeNode(2))?

from typing import Optional

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

def isSymmetric(root: Optional[TreeNode]) -> bool:
    def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
        if not t1 or not t2:
            return t1 == t2
        if t1.val != t2.val:
            return False
        return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)

    return isMirror(root.left, root.right) if root else True

root = TreeNode(1, TreeNode(2), TreeNode(2))
print(isSymmetric(root))  # What is the output?

easy

A. false

B. Raises an exception

C. null

D. true

Solution

1. Step 1: Trace isMirror on root.left and root.right nodes with value 2

   Both nodes exist and have equal values, so recursion continues.

2. Step 2: Recursively check left.left vs right.right and left.right vs right.left (both null)

   Since both pairs are null, isMirror returns true for these calls, so overall returns true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Symmetric tree with equal child nodes returns true [OK]

Hint: Symmetric tree with equal children returns true [OK]

Common Mistakes:

• Confusing null checks causing exceptions
• Returning false prematurely on equal nodes
• Misreading recursion base cases

4. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?

medium

A. Line 1: Missing check for empty root before traversal

B. Line 7: Incorrectly pushing node.left without null check

C. Line 12: Comparing last_visited with peek.right incorrectly

D. Line 16: Using abs difference without considering null children

Solution

1. Step 1: Identify handling of empty tree

   The code does not check if root is None before starting traversal, which can cause errors or incorrect results.

2. Step 2: Verify other lines

   Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing early return for empty root causes bug [OK]

Hint: Always check for empty root before traversal [OK]

Common Mistakes:

• Forgetting to handle empty tree as balanced
• Incorrectly comparing last_visited causing infinite loops
• Not defaulting heights for null children

5. Suppose you want to perform inorder traversal on a binary tree where nodes can have parent pointers but no left or right child pointers. Which approach correctly produces the inorder sequence without recursion or extra stack?

hard

A. Use Morris traversal by creating threads on parent pointers instead of child pointers.

B. Use breadth-first search since parent pointers allow level order traversal.

C. Use recursive traversal ignoring parent pointers, which will fail due to missing child links.

D. Use iterative traversal with a pointer to the current node and track previously visited node to decide traversal direction.

Solution

1. Step 1: Understand traversal constraints

   Without left/right child pointers, Morris traversal is not applicable since it relies on child links.

2. Step 2: Use parent pointers to simulate traversal

   By tracking current and previously visited nodes, we can move up or down the tree to simulate inorder traversal iteratively.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking previous node enables correct traversal without extra space [OK]

Hint: Parent pointers + prev node tracking enable traversal [OK]

Common Mistakes:

• Trying to create threads on parent pointers
• Using recursion without child pointers
• Confusing BFS with inorder traversal