Vertical Width of a Binary Tree

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

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

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?