Vertical Width of a Binary Tree

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Find number of distinct column indices in vertical traversal of binary tree.

Algorithm

1DFS tracking column: left child = col-1, right child = col+1. Track min and max col. Width = max-min+1.

Common Pitfalls

•O(n) DFS. Track min and max horizontal distance from root. Width = max_col - min_col + 1.

Vertical Width of a Binary Tree.java

Java

// Approach: DFS tracking horizontal distances. Width = max HD - min HD + 1.
// Time: O(n) Space: O(n)
class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    public int verticalWidth(Node root) {
        if (root == null)
            return 0;

        int[] a = new int[2];
        dfs(root, a, 0);

        return a[1] - a[0] + 1;
    }

    private void dfs(Node root, int[] a, int curr) {
        if (root == null)
            return;

        if (root.left != null)
            a[0] = Math.min(curr - 1, a[0]);

        if (root.right != null)
            a[1] = Math.max(curr + 1, a[1]);

        dfs(root.left, a, curr - 1);
        dfs(root.right, a, curr + 1);
    }
}

Was this solution helpful?