DEV Community: Jaspreet singh

Balanced Binary Tree

Jaspreet singh — Mon, 06 Jul 2026 16:50:23 +0000

Problem Statement

Given the root of a binary tree, determine whether it is height-balanced.

A binary tree is balanced if:

For every node,

| Left Height - Right Height | ≤ 1

Brute Force Intuition

In an interview, you can explain it like this:

For every node, calculate the height of its left and right subtrees. If the height difference is more than 1, the tree is not balanced.

The drawback is that the height of the same subtree is computed repeatedly.

Complexity

Time Complexity: O(N²)
Space Complexity: O(H)

Brute Force Code

class Solution {

    public boolean isBalanced(TreeNode root) {

        if (root == null)
            return true;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        if (Math.abs(leftHeight - rightHeight) > 1)
            return false;

        return isBalanced(root.left) &&
               isBalanced(root.right);
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

        return 1 + Math.max(
                height(root.left),
                height(root.right));
    }
}

Moving Towards the Optimal Approach

Notice that while calculating:

Height

we can also determine whether the subtree is balanced.

Instead of returning only the height,

return:

-1

whenever an unbalanced subtree is found.

This allows us to stop checking further.

Pattern Recognition

Whenever you see:

Balanced Tree
Height Difference
Height of Binary Tree

Think:

Postorder DFS

Key Observation

For every node:

Compute:

Left Height

↓

Right Height

If either subtree is already unbalanced:

Return -1

If:

|Left Height - Right Height| > 1

Again:

Return -1

Otherwise,

return the current height.

Optimal Approach

Step 1

Recursively compute:

Left Height

Step 2

Recursively compute:

Right Height

Step 3

If either returns:

-1

the tree is already unbalanced.

Step 4

If height difference exceeds:

return:

-1

Otherwise,

return:

1 + Math.max(leftHeight, rightHeight);

Optimal Java Solution

class Solution {

    public boolean isBalanced(TreeNode root) {

        return height(root) != -1;
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        if (leftHeight == -1 ||
            rightHeight == -1)
            return -1;

        if (Math.abs(leftHeight -
                     rightHeight) > 1)
            return -1;

        return 1 + Math.max(leftHeight,
                            rightHeight);
    }
}

Dry Run

Node 4

Left = 0

Right = 0

Height = 1

Node 2

Left = 1

Right = 0

Difference = 1

Balanced

Height = 2

Root 1

Left = 2

Right = 1

Difference = 1

Balanced

Answer:

true

Unbalanced Example

Node 1:

Left Height = 2

Right Height = 0

Difference = 2

Return -1

Answer:

false

Why Returning -1 Works?

Instead of checking balance separately,

the recursion combines two tasks:

Compute Height

+

Detect Imbalance

The moment an unbalanced subtree is found,

-1 propagates upward,

avoiding unnecessary calculations.

Every node is visited exactly once.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

Where:

N = Number of Nodes
H = Height of the Tree

Interview One-Liner

Use postorder DFS to compute subtree heights, returning -1 whenever an imbalance is detected so the result propagates upward immediately.

Pattern Learned

Postorder DFS

↓

Left Height

↓

Right Height

↓

Check Difference

↓

Return Height

or

-1

Memory Trick

Think:

Go Left

↓

Go Right

↓

Difference > 1 ?

↓

Return -1

↓

Else Return Height

Mental Model

Leaf

↓

Returns Height

↓

Parent

↓

Checks Balance

↓

Returns Height

or

-1

Whenever you hear:

"Balanced Binary Tree"

your brain should immediately think:

Postorder DFS + Return Height or -1

Diameter of a Binary Tree

Jaspreet singh — Mon, 06 Jul 2026 16:49:10 +0000

Problem Statement

Given the root of a binary tree, return the diameter of the tree.

The diameter is the length of the longest path between any two nodes in the tree.

Note: The path may or may not pass through the root.

Brute Force Intuition

In an interview, you can explain it like this:

For every node, calculate the height of its left subtree and right subtree. The diameter passing through that node is:

Left Height + Right Height

Take the maximum among all nodes.

The problem is that height is recomputed for every node, leading to repeated work.

Complexity

Time Complexity: O(N²)
Space Complexity: O(H)

Brute Force Code

class Solution {

    public int diameterOfBinaryTree(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        int currentDiameter =
                leftHeight + rightHeight;

        int leftDiameter =
                diameterOfBinaryTree(root.left);

        int rightDiameter =
                diameterOfBinaryTree(root.right);

        return Math.max(currentDiameter,
                Math.max(leftDiameter,
                         rightDiameter));
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

        return 1 + Math.max(
                height(root.left),
                height(root.right));
    }
}

Moving Towards the Optimal Approach

Notice that while computing:

Height

we already visit every node exactly once.

Why calculate height separately?

Instead,

while returning the height,

also update the maximum diameter.

One DFS can compute both.

Pattern Recognition

Whenever you see:

Diameter
Longest Path
Height of Tree

Think:

Postorder DFS

Key Observation

For every node:

Longest Path Through Node

=

Left Height

+

Right Height

At the same time,

return:

Current Height

=

1 + max(Left Height, Right Height)

Optimal Approach

Step 1

Recursively compute:

Left Height

Step 2

Recursively compute:

Right Height

Step 3

Update:

diameter = Math.max(diameter,
                    leftHeight + rightHeight);

Step 4

Return:

1 + Math.max(leftHeight, rightHeight);

Optimal Java Solution

class Solution {

    int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {

        height(root);

        return diameter;
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        diameter = Math.max(diameter,
                            leftHeight + rightHeight);

        return 1 + Math.max(leftHeight,
                            rightHeight);
    }
}

Dry Run

Node 4

Left = 0

Right = 0

Height = 1

Diameter = 0

Node 5

Height = 1

Node 2

Left Height = 1

Right Height = 1

Diameter = 2

Height = 2

Root 1

Left Height = 2

Right Height = 1

Diameter =

2 + 1

=

3

Final Answer:

Path:

4 → 2 → 1 → 3

Why One DFS Works?

Each recursive call already computes the height of its subtree.

While returning that height,

we can immediately compute the longest path passing through the current node.

This eliminates repeated height calculations.

Every node is visited exactly once.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

Where:

N = Number of Nodes
H = Height of the Tree

Interview One-Liner

Compute subtree heights using postorder DFS and update the diameter at each node as the sum of its left and right subtree heights.

Pattern Learned

Postorder DFS

↓

Left Height

↓

Right Height

↓

Update Diameter

↓

Return Height

Memory Trick

Think:

Go Left

↓

Go Right

↓

Diameter = Left + Right

↓

Return Height

Mental Model

Leaf

↓

Returns Height

↓

Parent

↓

Updates Diameter

↓

Returns Height

↓

Repeat

Whenever you hear:

"Diameter of Binary Tree"

your brain should immediately think:

Postorder DFS + Height Calculation

Maximum Depth of a Binary Tree

Jaspreet singh — Mon, 06 Jul 2026 16:42:37 +0000

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 down to the farthest leaf node.

Brute Force Intuition

In an interview, you can explain it like this:

Traverse every root-to-leaf path, calculate its length, and keep track of the maximum length found.

This works because the deepest root-to-leaf path represents the height of the tree.

Complexity

Time Complexity: O(N)
Space Complexity: O(H)

Moving Towards the Optimal Approach

Observe that the depth of a node depends only on:

Depth of Left Subtree

↓

Depth of Right Subtree

If we already know these two values,

the answer for the current node is simply:

1 + Maximum of Both

This naturally leads to a recursive solution.

Pattern Recognition

Whenever you see:

Height of Tree
Maximum Depth
Longest Root-to-Leaf Path

Think:

DFS + Recursion

Key Observation

For every node:

Height

=

1

+

max(

Left Height,

Right Height

)

Base Case:

NULL

↓

Height = 0

Optimal Approach

Step 1

Recursively calculate:

Left Height

Step 2

Recursively calculate:

Right Height

Step 3

Return:

1 + Math.max(leftHeight, rightHeight);

Optimal Java Solution

class Solution {

    public int maxDepth(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = maxDepth(root.left);

        int rightHeight = maxDepth(root.right);

        return 1 + Math.max(leftHeight,
                            rightHeight);
    }
}

Dry Run

Node 9

Left = 0

Right = 0

Height = 1

Node 20

Left = 1

Right = 1

Height = 2

Root 3

Left = 1

Right = 2

Height =

1 + max(1,2)

=

3

Final Answer:

Why DFS Works?

The height of every node depends only on the heights of its children.

DFS computes the answer from the bottom up.

Leaf nodes return:

and each parent builds its height using its children's heights.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

Where:

N = Number of Nodes
H = Height of the Tree

Interview One-Liner

Use DFS to recursively compute the heights of the left and right subtrees, then return one plus the maximum of both.

Pattern Learned

DFS

↓

Left Height

↓

Right Height

↓

1 + Maximum

Memory Trick

Think:

Go Left

↓

Go Right

↓

Take Maximum

↓

Add One

Mental Model

Leaf

↓

Returns 1

↓

Parent

↓

1 + max(Left, Right)

↓

Root

Whenever you hear:

"Maximum Depth" or "Height of Binary Tree"

your brain should immediately think:

DFS + 1 + max(Left, Right)

Level Order Traversal of a Binary Tree

Jaspreet singh — Mon, 06 Jul 2026 16:39:08 +0000

Problem Statement

Given the root of a binary tree, return its level order traversal.

Nodes should be traversed:

Level by Level

↓

Left to Right

Brute Force Intuition

In an interview, you can explain it like this:

Find the height of the tree. Then, for every level, recursively print all nodes at that level.

Although correct, every level requires traversing the tree again, leading to unnecessary repeated work.

Complexity

Time Complexity: O(N²) (Worst Case - Skewed Tree)
Space Complexity: O(H)

Brute Force Code

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> ans = new ArrayList<>();

        int height = getHeight(root);

        for (int i = 1; i <= height; i++) {

            List<Integer> level = new ArrayList<>();

            printLevel(root, i, level);

            ans.add(level);
        }

        return ans;
    }

    private int getHeight(TreeNode root) {

        if (root == null)
            return 0;

        return 1 + Math.max(
                getHeight(root.left),
                getHeight(root.right));
    }

    private void printLevel(TreeNode root,
                            int level,
                            List<Integer> list) {

        if (root == null)
            return;

        if (level == 1) {

            list.add(root.val);

            return;
        }

        printLevel(root.left,
                   level - 1,
                   list);

        printLevel(root.right,
                   level - 1,
                   list);
    }
}

Moving Towards the Optimal Approach

Notice that we don't need to repeatedly traverse the tree.

Instead,

process nodes exactly in the order they appear:

Level by Level

This is exactly what:

Breadth First Search (BFS)

does.

Pattern Recognition

Whenever you see:

Level Order Traversal
Minimum Levels
Process Tree Level Wise

Think:

Queue + BFS

Key Observation

Use a queue.

Initially:

Queue

↓

Root

For every level:

size = queue.size();

Process exactly:

size Nodes

These nodes belong to the current level.

Their children become the next level.

Optimal Approach

Step 1

Push the root into the queue.

Step 2

For every level:

size = queue.size();

Step 3

Process all nodes of the current level.

Store them into a list.

Step 4

Push:

Left Child

↓

Right Child

into the queue.

Optimal Java Solution

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<TreeNode> q = new LinkedList<>();

        q.offer(root);

        while (!q.isEmpty()) {

            int size = q.size();

            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {

                TreeNode curr = q.poll();

                level.add(curr.val);

                if (curr.left != null)
                    q.offer(curr.left);

                if (curr.right != null)
                    q.offer(curr.right);
            }

            ans.add(level);
        }

        return ans;
    }
}

Dry Run

Level 1

Queue:

Output:

[3]

Level 2

Queue:

9

20

Output:

[9,20]

Level 3

Queue:

15

7

Output:

[15,7]

Final Answer:

[
 [3],
 [9,20],
 [15,7]
]

Why BFS Works?

A queue follows:

FIFO

Nodes are processed in the exact order they are discovered.

Processing one queue size at a time naturally separates the traversal into individual levels.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(N)

Interview One-Liner

Perform a breadth-first traversal using a queue, processing one level at a time by iterating over the current queue size.

Pattern Learned

Queue

↓

Process One Level

↓

Push Children

↓

Repeat

Memory Trick

Think:

Queue

↓

Current Level Size

↓

Process Nodes

↓

Push Children

↓

Next Level

Mental Model

Root

↓

Queue

↓

One Level

↓

Next Level

↓

Repeat

Whenever you hear:

"Traverse the tree level by level"

your brain should immediately think:

Breadth First Search (BFS) + Queue

Maximum Width of Binary Tree

Jaspreet singh — Mon, 06 Jul 2026 16:37:38 +0000

Given the root of a binary tree, return the **## Problem Statement

Given the root of a binary tree, return the maximum width of the tree.

The width of a level is defined as:

Distance between the leftmost
and rightmost non-null nodes
(including null nodes in between).

Brute Force Intuition

In an interview, you can explain it like this:

Perform a level-order traversal and count the number of nodes at each level.

However, this is incorrect because missing (null) nodes between two existing nodes also contribute to the width.

Example:

Level 3 has only two nodes,

but its width is:

not 2.

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

Treat the binary tree as if it were stored in an array.

Assign every node an index.

Rules:

Root → 0

For every node:

Left Child

↓

2 * index + 1

Right Child

↓

2 * index + 2

Now,

Width of a level becomes:

Last Index

-

First Index

+

1

Pattern Recognition

Whenever you see:

Width of Binary Tree
Complete Binary Tree Positioning

Think:

Level Order Traversal + Indexing

Key Observation

Store inside the queue:

(Node, Index)

For every level:

First Index

↓

Last Index

Width:

last - first + 1;

To prevent integer overflow,

normalize indices at every level.

Optimal Approach

Step 1

Perform BFS.

Queue stores:

(Node, Index)

Step 2

For every level,

store:

Minimum Index

Subtract it from every index.

This keeps numbers small.

Step 3

Track:

First Index

↓

Last Index

Step 4

Update answer:

last - first + 1;

Optimal Java Solution

class Pair {

    TreeNode node;
    int index;

    Pair(TreeNode node, int index) {

        this.node = node;
        this.index = index;
    }
}

class Solution {

    public int widthOfBinaryTree(TreeNode root) {

        if (root == null)
            return 0;

        Queue<Pair> q = new LinkedList<>();

        q.offer(new Pair(root, 0));

        int ans = 0;

        while (!q.isEmpty()) {

            int size = q.size();

            int minIndex = q.peek().index;

            int first = 0;
            int last = 0;

            for (int i = 0; i < size; i++) {

                Pair curr = q.poll();

                int index = curr.index - minIndex;

                if (i == 0)
                    first = index;

                if (i == size - 1)
                    last = index;

                if (curr.node.left != null)

                    q.offer(new Pair(
                        curr.node.left,
                        2 * index + 1));

                if (curr.node.right != null)

                    q.offer(new Pair(
                        curr.node.right,
                        2 * index + 2));
            }

            ans = Math.max(ans,
                           last - first + 1);
        }

        return ans;
    }
}

Dry Run

          1
        /   \
       2     3
      /       \
     4         5

Assign indices:

          0
        /   \
       1     2
      /       \
     3         6

Level 1

Indices:

Width:

Level 2

Indices:

1

2

Width:

Level 3

Indices:

3

6

Width:

Answer:

Why Indexing Works?

The assigned indices represent the positions of nodes in a complete binary tree.

Even if some nodes are missing,

their positions are preserved.

Thus,

Last Index

-

First Index

+

1

correctly measures the actual width.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(N)

Interview One-Liner

Perform a level-order traversal while assigning complete binary tree indices to each node. The width of each level is the difference between the first and last indices plus one.

Pattern Learned

Level Order

↓

Assign Indices

↓

First Index

↓

Last Index

↓

Maximum Width

Memory Trick

Think:

Root → 0

↓

Left = 2i + 1

↓

Right = 2i + 2

↓

Width

=

Last - First + 1

Mental Model

BFS

↓

(Node, Index)

↓

Track First & Last

↓

Update Maximum Width

Whenever you hear:

"Maximum Width of Binary Tree"

your brain should immediately think:

Level Order Traversal + Complete Binary Tree Indexing .

The width of a level is defined as:

Distance between the leftmost
and rightmost non-null nodes
(including null nodes in between).

Brute Force Intuition

In an interview, you can explain it like this:

Perform a level-order traversal and count the number of nodes at each level.

However, this is incorrect because missing (null) nodes between two existing nodes also contribute to the width.

Example:

Level 3 has only two nodes,

but its width is:

not 2.

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

Treat the binary tree as if it were stored in an array.

Assign every node an index.

Rules:

Root → 0

For every node:

Left Child

↓

2 * index + 1

Right Child

↓

2 * index + 2

Now,

Width of a level becomes:

Last Index

-

First Index

+

1

Pattern Recognition

Whenever you see:

Width of Binary Tree
Complete Binary Tree Positioning

Think:

Level Order Traversal + Indexing

Key Observation

Store inside the queue:

(Node, Index)

For every level:

First Index

↓

Last Index

Width:

last - first + 1;

To prevent integer overflow,

normalize indices at every level.

Optimal Approach

Step 1

Perform BFS.

Queue stores:

(Node, Index)

Step 2

For every level,

store:

Minimum Index

Subtract it from every index.

This keeps numbers small.

Step 3

Track:

First Index

↓

Last Index

Step 4

Update answer:

last - first + 1;

Optimal Java Solution

class Pair {

    TreeNode node;
    int index;

    Pair(TreeNode node, int index) {

        this.node = node;
        this.index = index;
    }
}

class Solution {

    public int widthOfBinaryTree(TreeNode root) {

        if (root == null)
            return 0;

        Queue<Pair> q = new LinkedList<>();

        q.offer(new Pair(root, 0));

        int ans = 0;

        while (!q.isEmpty()) {

            int size = q.size();

            int minIndex = q.peek().index;

            int first = 0;
            int last = 0;

            for (int i = 0; i < size; i++) {

                Pair curr = q.poll();

                int index = curr.index - minIndex;

                if (i == 0)
                    first = index;

                if (i == size - 1)
                    last = index;

                if (curr.node.left != null)

                    q.offer(new Pair(
                        curr.node.left,
                        2 * index + 1));

                if (curr.node.right != null)

                    q.offer(new Pair(
                        curr.node.right,
                        2 * index + 2));
            }

            ans = Math.max(ans,
                           last - first + 1);
        }

        return ans;
    }
}

Dry Run

          1
        /   \
       2     3
      /       \
     4         5

Assign indices:

          0
        /   \
       1     2
      /       \
     3         6

Level 1

Indices:

Width:

Level 2

Indices:

1

2

Width:

Level 3

Indices:

3

6

Width:

Answer:

Why Indexing Works?

The assigned indices represent the positions of nodes in a complete binary tree.

Even if some nodes are missing,

their positions are preserved.

Thus,

Last Index

-

First Index

+

1

correctly measures the actual width.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(N)

Interview One-Liner

Perform a level-order traversal while assigning complete binary tree indices to each node. The width of each level is the difference between the first and last indices plus one.

Pattern Learned

Level Order

↓

Assign Indices

↓

First Index

↓

Last Index

↓

Maximum Width

Memory Trick

Think:

Root → 0

↓

Left = 2i + 1

↓

Right = 2i + 2

↓

Width

=

Last - First + 1

Mental Model

BFS

↓

(Node, Index)

↓

Track First & Last

↓

Update Maximum Width

Whenever you hear:

"Maximum Width of Binary Tree"

your brain should immediately think:

Level Order Traversal + Complete Binary Tree Indexing

Root to Leaf Path

Jaspreet singh — Sun, 05 Jul 2026 17:44:01 +0000

Problem Statement

Given the root of a binary tree, print all root-to-leaf paths.

A path starts at the root and ends at a leaf node.

Brute Force Intuition

In an interview, you can explain it like this:

Traverse the tree while maintaining the current path. Whenever a leaf node is reached, store the path.

Since every node belongs to exactly one traversal path, DFS naturally fits.

Complexity

Time Complexity: O(N)
Space Complexity: O(H)

Moving Towards the Optimal Approach

Observe that a path changes while moving down the tree.

Whenever recursion returns,

the last node should be removed.

This is exactly:

Backtracking

Pattern Recognition

Whenever you see:

Root to Leaf
Generate All Paths
Explore Every Possibility

Think:

DFS + Backtracking

Key Observation

Maintain:

Current Path

Whenever:

Leaf Node

is reached,

store a copy of the path.

After exploring,

remove the current node.

Optimal Approach

Step 1

Add current node.

Step 2

If leaf:

Store Path

Step 3

Explore:

Left

↓

Right

Step 4

Backtrack.

path.remove(path.size()-1);

Optimal Java Solution

class Solution {

    public static ArrayList<ArrayList<Integer>>
    Paths(Node root) {

        ArrayList<ArrayList<Integer>> ans =
                new ArrayList<>();

        dfs(root,
            new ArrayList<>(),
            ans);

        return ans;
    }

    static void dfs(Node root,
                    ArrayList<Integer> path,
                    ArrayList<ArrayList<Integer>> ans) {

        if (root == null)
            return;

        path.add(root.data);

        if (root.left == null &&
            root.right == null) {

            ans.add(new ArrayList<>(path));

        } else {

            dfs(root.left, path, ans);

            dfs(root.right, path, ans);
        }

        path.remove(path.size() - 1);
    }
}

Dry Run

Current Path:

↓

1 2

↓

1 2 4

Leaf:

Store:

[1,2,4]

Backtrack:

1 2

↓

Explore:

Store:

[1,3]

Final Answer:

[[1,2,4],[1,3]]

Why Backtracking Works?

Every recursive call adds one node to the path.

Once that subtree is completely explored,

the node is removed,

allowing the same path list to be reused for other branches.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

Interview One-Liner

Use DFS with backtracking by maintaining the current path, storing it at every leaf node, and removing the node while returning from recursion.

Pattern Learned

DFS

↓

Current Path

↓

Leaf

↓

Store Copy

↓

Backtrack

Memory Trick

Think:

Visit Node

↓

Add To Path

↓

Leaf?

↓

Store Copy

↓

Remove Node

Mental Model

DFS

↓

Path

↓

Leaf

↓

Answer

↓

Backtrack

Whenever you hear:

"Print all root-to-leaf paths"

your brain should immediately think:

DFS + Backtracking

Vertical Order Traversal

Jaspreet singh — Sun, 05 Jul 2026 17:41:37 +0000

leetcode.com

Problem Statement

Given the root of a binary tree, return its vertical order traversal.

Rules:

Nodes are grouped by their column (Horizontal Distance).
If multiple nodes share the same row and column, sort them by value.

Brute Force Intuition

In an interview, you can explain it like this:

Traverse every node, store its row and column information, then sort all collected nodes based on column, row, and value.

Although correct, sorting all nodes together becomes expensive.

Complexity

Time Complexity: O(N log N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

Observe that every node has:

Column (Horizontal Distance)

+

Row (Depth)

If we store nodes using:

Column

↓

Row

↓

Values

we can build the answer naturally.

Pattern Recognition

Whenever you see:

Vertical Traversal
Column-wise Traversal
Horizontal Distance

Think:

BFS + Ordered Maps

Key Observation

Assign coordinates:

Root

↓

(Row = 0, Col = 0)

Rules:

Left Child

↓

(Row + 1, Col - 1)

--------------------

Right Child

↓

(Row + 1, Col + 1)

Store nodes as:

TreeMap<
    Column,
    TreeMap<
        Row,
        PriorityQueue<Values>
    >
>

Optimal Approach

Step 1

Perform BFS.

Store:

(Node, Row, Column)

Step 2

Insert into:

column

↓

row

↓

priority queue

Step 3

Traverse:

Columns

↓

Rows

↓

Sorted Values

Optimal Java Solution

class Pair {

    TreeNode node;
    int row;
    int col;

    Pair(TreeNode node,
         int row,
         int col) {

        this.node = node;
        this.row = row;
        this.col = col;
    }
}

class Solution {

    public List<List<Integer>> verticalTraversal(TreeNode root) {

        TreeMap<Integer,
        TreeMap<Integer,
        PriorityQueue<Integer>>> map =
                new TreeMap<>();

        Queue<Pair> q = new LinkedList<>();

        q.offer(new Pair(root, 0, 0));

        while (!q.isEmpty()) {

            Pair curr = q.poll();

            map.putIfAbsent(curr.col,
                    new TreeMap<>());

            map.get(curr.col)
               .putIfAbsent(curr.row,
                    new PriorityQueue<>());

            map.get(curr.col)
               .get(curr.row)
               .offer(curr.node.val);

            if (curr.node.left != null)

                q.offer(new Pair(
                        curr.node.left,
                        curr.row + 1,
                        curr.col - 1));

            if (curr.node.right != null)

                q.offer(new Pair(
                        curr.node.right,
                        curr.row + 1,
                        curr.col + 1));
        }

        List<List<Integer>> ans =
                new ArrayList<>();

        for (TreeMap<Integer,
             PriorityQueue<Integer>> rows
             : map.values()) {

            List<Integer> list =
                    new ArrayList<>();

            for (PriorityQueue<Integer> pq
                    : rows.values()) {

                while (!pq.isEmpty())

                    list.add(pq.poll());
            }

            ans.add(list);
        }

        return ans;
    }
}

Dry Run

Coordinates:

9

↓

(-1,1)

3

↓

(0,0)

15

↓

(0,2)

20

↓

(1,1)

7

↓

(2,2)

Vertical Order:

Answer:

[[9],[3,15],[20],[7]]

Why BFS + Ordered Maps Work?

Every node is assigned:

Column

↓

Row

TreeMap automatically sorts:

Columns

↓

Rows

PriorityQueue handles nodes that share the same row and column.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log N)
Space Complexity	O(N)

Interview One-Liner

Perform BFS while tracking row and column indices, then store nodes in nested TreeMaps with a PriorityQueue to maintain the required ordering.

Pattern Learned

BFS

↓

(Row, Column)

↓

Ordered Maps

↓

Vertical Traversal

Memory Trick

Think:

Node

↓

(Row, Column)

↓

TreeMap

↓

PriorityQueue

↓

Answer

Mental Model

Tree

↓

Assign Coordinates

↓

Group By Column

↓

Sort By Row

↓

Output

Whenever you hear:

"Vertical Order Traversal"

your brain should immediately think:

BFS + (Row, Column) Coordinates + TreeMap

Morris Pre Order Traversal

Jaspreet singh — Sat, 04 Jul 2026 10:42:35 +0000

Problem Statement

Given the root of a binary tree, return its preorder traversal.

The challenge is to perform the traversal:

Without Recursion

Without Stack

O(1) Extra Space

Brute Force Intuition

In an interview, you can explain it like this:

Perform a normal recursive preorder traversal.

Traversal order:

Root

↓

Left

↓

Right

Recursion naturally remembers the parent nodes.

Complexity

Time Complexity: O(N)
Space Complexity: O(H)

Better Approach

Use an explicit stack.

Visit:

Root

↓

Left

↓

Right

Complexity

Time Complexity: O(N)
Space Complexity: O(H)

Moving Towards the Optimal Approach

Can we perform preorder traversal without:

Recursion

OR

Stack?

Yes.

Instead of using recursion,

temporarily connect the inorder predecessor back to the current node.

This temporary connection is called a:

Thread

Unlike Morris Inorder,

here we visit the node before moving to the left subtree.

Pattern Recognition

Whenever you see:

Binary Tree Traversal
O(1) Extra Space
No Stack
No Recursion

Think:

Morris Traversal

Key Observation

For every node:

Case 1

No Left Child

Visit it immediately.

Move:

Right

Case 2

Has Left Child

Find its:

Inorder Predecessor

(the rightmost node of the left subtree)

If predecessor's right is:

NULL

Visit current node.

Create a temporary thread.

Predecessor

↓

Current

Move:

Left

If predecessor already points to current,

remove the thread,

move to the right subtree.

Notice:

Unlike Morris Inorder,

we do not visit the node while removing the thread.

Visualization

Original Tree

Temporary Thread

3
 \
  4

After returning,

the thread is removed,

restoring the original tree.

Optimal Java Solution

class Solution {

    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        TreeNode curr = root;

        while (curr != null) {

            if (curr.left == null) {

                ans.add(curr.val);

                curr = curr.right;

            } else {

                TreeNode pred = curr.left;

                while (pred.right != null &&
                       pred.right != curr) {

                    pred = pred.right;
                }

                if (pred.right == null) {

                    ans.add(curr.val);

                    pred.right = curr;

                    curr = curr.left;

                } else {

                    pred.right = null;

                    curr = curr.right;
                }
            }
        }

        return ans;
    }
}

Dry Run

Tree

Step 1

Current:

Visit:

Create thread:

3 → 4

Move left.

Step 2

Current:

Visit:

Create thread:

1 → 2

Move left.

Step 3

Current:

No left child.

Visit:

Move through thread.

Step 4

Back to:

Remove thread.

Move right.

Visit:

Return through thread.

Visit:

Final Traversal

Why Morris Preorder Works?

Instead of using recursion,

we temporarily connect:

Inorder Predecessor

↓

Current Node

Since preorder visits the root first,

we process the node when creating the thread.

When we return,

the thread is removed,

and the original tree is restored.

Each edge is traversed at most twice.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(1)

Interview One-Liner

Morris Preorder Traversal visits the node before creating a temporary thread to its inorder predecessor, achieving preorder traversal in O(1) extra space.

Pattern Learned

Need O(1) Space

↓

No Stack

↓

No Recursion

↓

Thread Binary Tree

↓

Visit Before Going Left

Memory Trick

Think:

Has Left Child?

↓

Find Predecessor

↓

Thread Exists?

↓

No

Visit Node

Create Thread

Go Left

----------------

Yes

Remove Thread

Go Right

Mental Model

Current

↓

Visit

↓

Thread

↓

Left

↓

Back

↓

Right

Whenever you hear:

"Preorder traversal without recursion or stack"

your brain should immediately think:

Morris Preorder Traversal

Bottom View of Binary Tree

Jaspreet singh — Sat, 04 Jul 2026 10:41:25 +0000

geeksforgeeks.org

Problem Statement

Given the root of a binary tree, return the nodes visible when the tree is viewed from the bottom.

For every horizontal distance (HD), the bottom-most node should be included.

Brute Force Intuition

In an interview, you can explain it like this:

Compute the horizontal distance of every node and store all nodes belonging to that distance along with their levels. Finally, choose the deepest node for every horizontal distance.

This works but requires storing multiple nodes for each horizontal distance.

Complexity

Time Complexity: O(N log N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that:

BFS

↓

Processes Nodes

Level by Level

Unlike Top View,

we don't want the first node.

We always want the:

Latest Node

encountered for every horizontal distance.

Since BFS visits deeper nodes later,

we simply overwrite the previous value.

Pattern Recognition

Whenever you see:

Bottom View
Top View
Vertical Traversal

Think:

Level Order Traversal + Horizontal Distance

Key Observation

Assign every node a:

Horizontal Distance (HD)

Rules:

Root → 0

Left Child → HD - 1

Right Child → HD + 1

Whenever we visit a node,

simply update:

map.put(hd, node.data);

The last value stored for an HD becomes the bottom view.

Optimal Approach

Step 1

Perform BFS.

Queue stores:

(Node, HD)

Step 2

Maintain:

TreeMap<Integer, Integer>

Key:

Horizontal Distance

Value:

Latest Node Value

Step 3

For every node:

map.put(hd, node.data);

Always overwrite.

Step 4

Traverse the TreeMap from left to right.

Optimal Java Solution

class Pair {

    Node node;
    int hd;

    Pair(Node node, int hd) {

        this.node = node;
        this.hd = hd;
    }
}

class Solution {

    public ArrayList<Integer> bottomView(Node root) {

        ArrayList<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<Pair> q = new LinkedList<>();

        TreeMap<Integer, Integer> map =
            new TreeMap<>();

        q.offer(new Pair(root, 0));

        while (!q.isEmpty()) {

            Pair curr = q.poll();

            map.put(curr.hd, curr.node.data);

            if (curr.node.left != null)

                q.offer(new Pair(
                    curr.node.left,
                    curr.hd - 1));

            if (curr.node.right != null)

                q.offer(new Pair(
                    curr.node.right,
                    curr.hd + 1));
        }

        ans.addAll(map.values());

        return ans;
    }
}

Dry Run

          1
        /   \
       2     3
      / \   / \
     4   5 6   7

Horizontal Distances:

4 → -2

2 → -1

1 → 0

3 → +1

7 → +2

While traversing:

HD = 0

1

↓

5

↓

6

Latest node:

Final Bottom View:

[4,2,6,3,7]

Why BFS Works?

BFS visits nodes level by level.

For each horizontal distance,

deeper nodes are processed later.

By continuously overwriting the value for each HD,

the last stored node naturally becomes the bottom-most visible node.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log N)
Space Complexity	O(N)

log N comes from inserting keys into the TreeMap.

Interview One-Liner

Perform a level-order traversal while tracking horizontal distances and overwrite the node value for each distance so the last node becomes the bottom view.

Pattern Learned

BFS

↓

Horizontal Distance

↓

Overwrite Node

↓

Bottom View

Memory Trick

Think:

Horizontal Distance

↓

Always Update

↓

Last Node Wins

Mental Model

Queue

↓

(Node, HD)

↓

Overwrite Map

↓

Answer

Whenever you hear:

"Bottom View of Binary Tree"

your brain should immediately think:

BFS + Horizontal Distance + Overwrite Every Time

Top View of Binary Tree | Level Order Traversal

Jaspreet singh — Sat, 04 Jul 2026 10:35:55 +0000

Problem Statement

Given the root of a binary tree, return the nodes visible when the tree is viewed from the top.

For every horizontal distance (HD), only the first node encountered should be included.

Brute Force Intuition

In an interview, you can explain it like this:

Compute the horizontal distance of every node and store all nodes belonging to the same horizontal distance. Finally, choose the topmost node for each horizontal distance.

This requires storing multiple nodes for every horizontal distance.

Complexity

Time Complexity: O(N log N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that:

BFS

↓

Processes Nodes

Level by Level

The first node encountered for a particular:

Horizontal Distance

will always be the topmost node.

So we only need to store it once.

Pattern Recognition

Whenever you see:

Top View
Bottom View
Vertical Traversal

Think:

Level Order Traversal + Horizontal Distance

Key Observation

Assign every node a:

Horizontal Distance (HD)

Rules:

Root → 0

Left Child → HD - 1

Right Child → HD + 1

If an HD appears for the first time,

store that node.

Ignore all future nodes with the same HD.

Optimal Approach

Step 1

Perform BFS.

Queue stores:

(Node, HD)

Step 2

Maintain:

TreeMap<Integer, Integer>

Key:

Horizontal Distance

Value:

Node Value

Step 3

If HD is not already present:

map.put(hd, node.data);

Step 4

Traverse the TreeMap from left to right.

Optimal Java Solution

class Pair {

    Node node;
    int hd;

    Pair(Node node, int hd) {

        this.node = node;
        this.hd = hd;
    }
}

class Solution {

    static ArrayList<Integer> topView(Node root) {

        ArrayList<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<Pair> q = new LinkedList<>();

        TreeMap<Integer, Integer> map =
            new TreeMap<>();

        q.offer(new Pair(root, 0));

        while (!q.isEmpty()) {

            Pair curr = q.poll();

            if (!map.containsKey(curr.hd)) {

                map.put(curr.hd,
                        curr.node.data);
            }

            if (curr.node.left != null)

                q.offer(new Pair(
                    curr.node.left,
                    curr.hd - 1));

            if (curr.node.right != null)

                q.offer(new Pair(
                    curr.node.right,
                    curr.hd + 1));
        }

        ans.addAll(map.values());

        return ans;
    }
}

Dry Run

          1
        /   \
       2     3
      / \   / \
     4   5 6   7

Horizontal Distances:

4 → -2

2 → -1

1 → 0

3 → +1

7 → +2

Nodes:

5

6

are ignored because:

HD already occupied

Final Answer:

[4,2,1,3,7]

Why BFS Works?

BFS visits nodes level by level.

The first node encountered at each horizontal distance is always the highest (topmost) node.

Once an HD is recorded,

it should never be replaced.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log N)
Space Complexity	O(N)

log N comes from inserting keys into the TreeMap.

Interview One-Liner

Perform a level-order traversal while tracking horizontal distances, and store only the first node encountered for each horizontal distance.

Pattern Learned

BFS

↓

Horizontal Distance

↓

First Node

↓

Top View

Memory Trick

Think:

Horizontal Distance

↓

Seen Before?

↓

No

↓

Store It

↓

Ignore Future Nodes

Mental Model

Queue

↓

(Node, HD)

↓

First Node at HD

↓

Answer

Whenever you hear:

"Top View of Binary Tree"

your brain should immediately think:

BFS + Horizontal Distance + First Node

Right View of a Binary Tree

Jaspreet singh — Sat, 04 Jul 2026 10:34:14 +0000

leetcode.com

Problem Statement

Given the root of a binary tree, return the nodes visible when the tree is viewed from the right side.

Only the last node at each level is visible.

Brute Force Intuition

In an interview, you can explain it like this:

Perform a level-order traversal (BFS). For every level, record the last node encountered.

Since BFS already processes nodes level by level, identifying the last node is straightforward.

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that during BFS:

Each Level

↓

Processed Together

If we know:

Level Size

then the last node processed at that level is exactly the right view.

Pattern Recognition

Whenever you see:

Left View
Right View
Level Wise Traversal

Think:

Level Order Traversal (BFS)

Key Observation

For every level:

Last Node

↓

Right View

Continue BFS until all levels are processed.

Optimal Approach

Step 1

Push the root into the queue.

Step 2

Process one level at a time.

size = queue.size();

Step 3

The last node:

i == size - 1

belongs to the right view.

Step 4

Push:

Left Child

↓

Right Child

into the queue.

Optimal Java Solution

class Solution {

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<TreeNode> q = new LinkedList<>();

        q.offer(root);

        while (!q.isEmpty()) {

            int size = q.size();

            for (int i = 0; i < size; i++) {

                TreeNode curr = q.poll();

                if (i == size - 1)
                    ans.add(curr.val);

                if (curr.left != null)
                    q.offer(curr.left);

                if (curr.right != null)
                    q.offer(curr.right);
            }
        }

        return ans;
    }
}

Dry Run

         1
       /   \
      2     3
     / \     \
    4   5     6

Level 1

Last Node:

Level 2

2 3

Last Node:

Level 3

4 5 6

Last Node:

Final Answer:

[1,3,6]

Why BFS Works?

BFS processes nodes level by level.

Since nodes are visited from left to right, the last node processed at every level is exactly the node visible from the right side.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(N)

Interview One-Liner

Perform a level-order traversal and record the last node encountered at every level.

Pattern Learned

Level Order

↓

Last Node

↓

Right View

Memory Trick

Think:

One Level

↓

Last Node

↓

Answer

Mental Model

Queue

↓

Process One Level

↓

Pick Last Node

↓

Continue

Whenever you hear:

"Right View of Binary Tree"

your brain should immediately think:

Level Order Traversal + Last Node of Every Level

Left View of a Binary Tree

Jaspreet singh — Sat, 04 Jul 2026 10:33:36 +0000

leetcode.com

Problem Statement

Given the root of a binary tree, return the nodes visible when the tree is viewed from the left side.

Only the first node at each level is visible.

Brute Force Intuition

In an interview, you can explain it like this:

Perform a level-order traversal (BFS). For every level, simply record the first node encountered.

Since BFS already processes nodes level by level, identifying the first node is straightforward.

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that during BFS:

Each Level

↓

Processed Together

If we know:

Level Size

then the very first node processed at that level is exactly the left view.

Pattern Recognition

Whenever you see:

Left View
Right View
Level Wise Processing

Think:

Level Order Traversal (BFS)

Key Observation

For every level:

First Node

↓

Left View

Continue BFS until all levels are processed.

Optimal Approach

Step 1

Push the root into a queue.

Step 2

Process one level at a time.

For every level:

size = queue.size();

Step 3

The first node:

i == 0

belongs to the left view.

Step 4

Push:

Left Child

↓

Right Child

into the queue.

Optimal Java Solution

class Solution {

    ArrayList<Integer> leftView(Node root) {

        ArrayList<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<Node> q = new LinkedList<>();

        q.offer(root);

        while (!q.isEmpty()) {

            int size = q.size();

            for (int i = 0; i < size; i++) {

                Node curr = q.poll();

                if (i == 0)
                    ans.add(curr.data);

                if (curr.left != null)
                    q.offer(curr.left);

                if (curr.right != null)
                    q.offer(curr.right);
            }
        }

        return ans;
    }
}

Dry Run

         1
       /   \
      2     3
     / \     \
    4   5     6

Level 1

First Node:

Level 2

2 3

First Node:

Level 3

4 5 6

First Node:

Final Answer:

[1,2,4]

Why BFS Works?

BFS processes the tree level by level.

Since nodes are visited from left to right,

the first node encountered at every level is exactly the node visible from the left side.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(N)

Interview One-Liner

Perform a level-order traversal and record the first node encountered at every level.

Pattern Learned

Level Order

↓

First Node

↓

Left View

Memory Trick

Think:

One Level

↓

First Node

↓

Answer

Mental Model

Queue

↓

Process One Level

↓

Pick First Node

↓

Continue

Whenever you hear:

"Left View of Binary Tree"

your brain should immediately think:

Level Order Traversal + First Node of Every Level

DEV Community: Jaspreet singh

Balanced Binary Tree

Problem Statement

Brute Force Intuition

Complexity

Brute Force Code

Moving Towards the Optimal Approach

Pattern Recognition

Key Observation

Optimal Approach

Step 1

Step 2

Step 3

Step 4

Optimal Java Solution

Dry Run

Node 4

Node 2

Root 1

Unbalanced Example

Why Returning -1 Works?

Complexity Analysis

Interview One-Liner

Pattern Learned

Similar Problems

Memory Trick

Mental Model

Diameter of a Binary Tree

Problem Statement

Brute Force Intuition

Complexity

Brute Force Code

Moving Towards the Optimal Approach

Pattern Recognition

Key Observation

Optimal Approach

Step 1

Step 2

Step 3

Step 4

Optimal Java Solution

Dry Run

Node 4

Node 5

Node 2

Root 1

Why One DFS Works?

Complexity Analysis

Interview One-Liner

Pattern Learned

Similar Problems

Memory Trick

Mental Model

Maximum Depth of a Binary Tree

Problem Statement

Brute Force Intuition

Complexity

Moving Towards the Optimal Approach

Pattern Recognition

Key Observation

Optimal Approach

Step 1

Step 2

Step 3

Optimal Java Solution

Dry Run

Node 9

Node 20

Root 3

Why DFS Works?

Complexity Analysis

Interview One-Liner

Pattern Learned

Similar Problems

Memory Trick

Mental Model

Level Order Traversal of a Binary Tree

Problem Statement

Brute Force Intuition

Complexity