Vertical Traversal of a Binary Tree

Last Updated : 7 Oct, 2025

Given the root of a binary Tree, Find its vertical traversal starting from the leftmost level to the rightmost level.

Note: If multiple nodes are at the same horizontal distance from the root and on the same level, they should be printed in the order they appear in a level-order traversal (top-to-bottom, left-to-right).

Here, Horizontal distance is calculated from the root to a specific node by counting how many times we move left or right along the unique path from the root to that node.

The formula for Horizontal distance from the root is given by:

Horizontal Distance = Number of right moves − Number of left moves in the path from the root to that node.

Examples:

Input:

Output: [[4], [2], [1, 5, 6, 11], [3, 8, 9], [7], [10]]
Explanation: The below image shows the horizontal distances used to print vertical traversal starting from the leftmost level to the rightmost level

Try it on GfG Practice

Table of Content

[Naive Approach] - Traversing the Tree for each vertical line
[Better Approach] - Using DFS and Sorting - O(n log(n)) Time and O(n) Space
[Expected Approach] - Using BFS - O(n) Time and O(n) Space

[Naive Approach] - Traversing the Tree for each vertical line

The idea is to traverse the tree once and get the minimum and maximum horizontal distance with respect to root. For the tree shown above example, minimum distance is -2 (for node with value 4) and maximum distance is 3 (For node with value 10).

Once we have maximum and minimum distances from root, we iterate for each vertical line at distance minimum to maximum from root, and for each vertical line traverse the tree and print the nodes which lie on that vertical line.

C++

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

// Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};

// Finds the minimum and maximum horizontal distance in the tree
void findMinMax(Node* node, int& min, int& max, int hd) {
  
    if (node == nullptr) return;

    if (hd < min) min = hd;
    else if (hd > max) max = hd;

    // Recur for left and right subtrees
    findMinMax(node->left, min, max, hd - 1);
    findMinMax(node->right, min, max, hd + 1);
}

// Collects all nodes at a given vertical distance in level-order
void collectVerticalLine(Node *root, int dist, vector<int>& line) {

      int hd = 0;

      // Create a queue for level order traversal
      queue<pair<Node*, int>> q;
      q.push({ root, 0 });

      int mn = 0, mx = 0;
      while (!q.empty()) {
        pair<Node*, int> curr = q.front();
        q.pop();

        Node* node = curr.first;
		hd = curr.second;
        if( hd == dist ) line.push_back(node->data);

        if (node->left)
              q.push({ node->left, hd - 1 });
        if (node->right)
              q.push({ node->right, hd + 1 });
      }
  
}    

// Returns the vertical order traversal of the tree
vector<vector<int>> verticalOrder(Node* root) {
    vector<vector<int>> res;

    int min = 0, max = 0;
    findMinMax(root, min, max, 0);

    for (int line = min; line <= max; line++) {
        vector<int> verticalNodes;
        
        // storing nodes for each vertical lines
        collectVerticalLine(root, line, verticalNodes);
        
        res.push_back(verticalNodes);
    }

    return res;
}

int main() {
  
    // Create binary tree
    //            1
    //          /   \
    //         2     3
    //        / \   / \
    //       4   5 6   7
    //            \  \   \
    //             8  9   10
    //            /
    //           11

    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->right->right = new Node(8);
    root->right->left->right = new Node(9);
    root->right->right->right = new Node(10);
    root->left->right->right->left = new Node(11);

    vector<vector<int>> res = verticalOrder(root);


    cout << "[";
    for(int i = 0;i < res.size(); i++) {
        cout << "[";
        vector<int> line = res[i];
        for( int j = 0; j < line.size(); j++ ) {
            cout << line[j];
            if( j != line.size()-1) cout << ", ";
        }
        cout << "]";
        if( i != res.size()-1) cout << ", ";
    }
    
    cout << "]";
    cout << endl;

    return 0;
}

Java

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

// Node Structure
class Node {
    int data;
    Node left, right;

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

class GFG {

    // Finds the minimum and maximum horizontal distance in the tree
    static void findMinMax(Node node, int[] min, int[] max, int hd) {
        if (node == null) return;

        if (hd < min[0]) min[0] = hd;
        else if (hd > max[0]) max[0] = hd;

        // Recur for left and right subtrees
        findMinMax(node.left, min, max, hd - 1);
        findMinMax(node.right, min, max, hd + 1);
    }

    // Collects all nodes at a given vertical distance in level-order
    static void collectVerticalLine(Node root, int dist, ArrayList<Integer> line) {
        int hd = 0;

        // Queue for level-order traversal
        Queue<ArrayList<Object>> q = new LinkedList<>();
        ArrayList<Object> first = new ArrayList<>();
        first.add(root);
        first.add(hd);
        q.add(first);

        while (!q.isEmpty()) {
            ArrayList<Object> curr = q.poll();
            Node node = (Node) curr.get(0);
            hd = (int) curr.get(1);

            if (hd == dist) line.add(node.data);

            if (node.left != null) {
                ArrayList<Object> leftNode = new ArrayList<>();
                leftNode.add(node.left);
                leftNode.add(hd - 1);
                q.add(leftNode);
            }
            if (node.right != null) {
                ArrayList<Object> rightNode = new ArrayList<>();
                rightNode.add(node.right);
                rightNode.add(hd + 1);
                q.add(rightNode);
            }
        }
    }

    // Returns the vertical order traversal of the tree
    static ArrayList<ArrayList<Integer>> verticalOrder(Node root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        int[] min = {0}, max = {0};
        findMinMax(root, min, max, 0);

        for (int line = min[0]; line <= max[0]; line++) {
            ArrayList<Integer> verticalNodes = new ArrayList<>();
            collectVerticalLine(root, line, verticalNodes);
            res.add(verticalNodes);
        }
        return res;
    }

    public static void main(String[] args) {

        // Create binary tree
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //       4   5 6   7
        //            \  \   \
        //             8  9   10
        //            /
        //           11

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.right = new Node(8);
        root.right.left.right = new Node(9);
        root.right.right.right = new Node(10);
        root.left.right.right.left = new Node(11);

        ArrayList<ArrayList<Integer>> res = verticalOrder(root);

        System.out.print("[");
        for (int i = 0; i < res.size(); i++) {
            System.out.print("[");
            ArrayList<Integer> line = res.get(i);
            for (int j = 0; j < line.size(); j++) {
                System.out.print(line.get(j));
                if (j != line.size() - 1) System.out.print(", ");
            }
            System.out.print("]");
            if (i != res.size() - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

Python

from collections import deque

# Node Structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Returns the vertical order traversal of the tree
def findMinMax(node, minmax, hd):
    if node is None:
        return

    if hd < minmax["min"]:
        minmax["min"] = hd
    elif hd > minmax["max"]:
        minmax["max"] = hd


    # Recur for left and right subtrees
    findMinMax(node.left, minmax, hd - 1)
    findMinMax(node.right, minmax, hd + 1)

# Collects all nodes at a given vertical distance in level-order
def collectVerticalLine(root, dist, line):
    hd = 0

    # Create a queue for level order traversal
    q = deque()
    q.append((root, 0))

    while q:
        node, hd = q.popleft()
        if hd == dist:
            line.append(node.data)

        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))

# Finds the minimum and maximum horizontal distance in the tree
def verticalOrder(root):
    res = []

    minmax = {"min": 0, "max": 0}
    findMinMax(root, minmax, 0)

    for line in range(minmax["min"], minmax["max"] + 1):
        verticalNodes = []
        collectVerticalLine(root, line, verticalNodes)
        res.append(verticalNodes)

    return res

if __name__ == "__main__":
    
    #  Create binary tree
    #             1
    #           /   \
    #          2     3
    #         / \   / \
    #       4   5 6   7
    #             \  \   \
    #              8  9   10
    #             /
    #           11
    
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    root.left.right.right = Node(8)
    root.right.left.right = Node(9)
    root.right.right.right = Node(10)
    root.left.right.right.left = Node(11)

    res = verticalOrder(root)

    print("[", end="")
    for i in range(len(res)):
        print("[", end="")
        line = res[i]
        for j in range(len(line)):
            print(line[j], end="")
            if j != len(line) - 1:
                print(", ", end="")
        print("]", end="")
        if i != len(res) - 1:
            print(", ", end="")
    print("]")

C#

using System;
using System.Collections.Generic;

// Node Structure
class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GFG {
    
    // Finds the minimum and maximum horizontal distance in the tree
    static void findMinMax(Node node, ref int min, ref int max, int hd) {
        if (node == null) return;

        if (hd < min) min = hd;
        else if (hd > max) max = hd;

        // Recur for left and right subtrees
        findMinMax(node.left, ref min, ref max, hd - 1);
        findMinMax(node.right, ref min, ref max, hd + 1);
    }
    
    // Collects all nodes at a given vertical distance in level-order
    static void collectVerticalLine(Node root, int dist, List<int> line) {
        int hd = 0;

        // Create a queue for level order traversal
        Queue<(Node, int)> q = new Queue<(Node, int)>();
        q.Enqueue((root, 0));

        while (q.Count > 0) {
            var curr = q.Dequeue();
            Node node = curr.Item1;
            hd = curr.Item2;

            if (hd == dist) line.Add(node.data);

            if (node.left != null) q.Enqueue((node.left, hd - 1));
            if (node.right != null) q.Enqueue((node.right, hd + 1));
        }
    }
    
    // Returns the vertical order traversal of the tree
    static List<List<int>> verticalOrder(Node root) {
        List<List<int>> res = new List<List<int>>();

        int min = 0, max = 0;
        findMinMax(root, ref min, ref max, 0);

        for (int line = min; line <= max; line++) {
            List<int> verticalNodes = new List<int>();
            collectVerticalLine(root, line, verticalNodes);
            res.Add(verticalNodes);
        }

        return res;
    }

    static void Main() {
        
        // Create binary tree
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //       4   5 6   7
        //            \  \   \
        //             8  9   10
        //            /
        //           11
    
    
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.right = new Node(8);
        root.right.left.right = new Node(9);
        root.right.right.right = new Node(10);
        root.left.right.right.left = new Node(11);

        List<List<int>> res = verticalOrder(root);

        Console.Write("[");
        for (int i = 0; i < res.Count; i++) {
            Console.Write("[");
            List<int> line = res[i];
            for (int j = 0; j < line.Count; j++) {
                Console.Write(line[j]);
                if (j != line.Count - 1) Console.Write(", ");
            }
            Console.Write("]");
            if (i != res.Count - 1) Console.Write(", ");
        }
        Console.WriteLine("]");
    }
}

JavaScript

// Node Structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Finds the minimum and maximum horizontal distance in the tree
function findMinMax(node, minmax, hd) {
    if (!node) return;

    if (hd < minmax.min) minmax.min = hd;
    else if (hd > minmax.max) minmax.max = hd;


    // Recur for left and right subtrees
    findMinMax(node.left, minmax, hd - 1);
    findMinMax(node.right, minmax, hd + 1);
}

// Collects all nodes at a given vertical distance in level-order
function collectVerticalLine(root, dist, line) {
    let hd = 0;


    // Create a queue for level order traversal
    let q = [];
    q.push([root, 0]);

    while (q.length > 0) {
        let [node, currHd] = q.shift();
        hd = currHd;

        if (hd === dist) line.push(node.data);

        if (node.left) q.push([node.left, hd - 1]);
        if (node.right) q.push([node.right, hd + 1]);
    }
}

// Returns the vertical order traversal of the tree
function verticalOrder(root) {
    let res = [];

    let minmax = { min: 0, max: 0 };
    findMinMax(root, minmax, 0);

    for (let line = minmax.min; line <= minmax.max; line++) {
        let verticalNodes = [];
        collectVerticalLine(root, line, verticalNodes);
        res.push(verticalNodes);
    }

    return res;
}

// Driver Code

// Create binary tree
//            1
//          /   \
//         2     3
//        / \   / \
//       4   5 6   7
//            \  \   \
//             8  9   10
//            /
//           11

let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.right.right = new Node(8);
root.right.left.right = new Node(9);
root.right.right.right = new Node(10);
root.left.right.right.left = new Node(11);

let res = verticalOrder(root);

process.stdout.write("[");
for (let i = 0; i < res.length; i++) {
    process.stdout.write("[");
    let line = res[i];
    for (let j = 0; j < line.length; j++) {
        process.stdout.write(line[j].toString());
        if (j !== line.length - 1) process.stdout.write(", ");
    }
    process.stdout.write("]");
    if (i !== res.length - 1) process.stdout.write(", ");
}
console.log("]");

Output

[[4], [2], [1, 5, 6, 11], [3, 8, 9], [7], [10]]

Time Complexity: O(n²), Time complexity of above algorithm is O(w*n) where w is width of Binary Tree and n is number of nodes in Binary Tree. In worst case, the value of w can be n.
Auxiliary Space: O(n), due to recursion stack.

[Better Approach] - Using DFS and Sorting - O(n log(n)) Time and O(n) Space

The idea is to traverse the tree using DFS and store the mapping of each horizontal distance to a list of pairs containing the node value and its level. These pairs are required so that nodes can later be printed in the correct order based on their level. Then, we sort the pairs based on their level as the order of nodes in the same level is maintained in DFS, but since DFS explores all nodes in depth before moving to other branches, the order of nodes by level is not naturally preserved.

C++

#include <iostream>
#include <vector>
#include <queue>   
#include <algorithm> 
#include <map>
using namespace std;

// Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};

// Performs DFS to map each node to its horizontal distance and level
void dfs(Node* root, int hd, int lvl, map<int, vector<pair<int,int>>>& verticalLines) {
    if (root == nullptr) return;

    // storing node value and level
    verticalLines[hd].push_back({root->data, lvl});

    // Recur for left and right subtrees
    dfs(root->left, hd - 1, lvl + 1, verticalLines);
    dfs(root->right, hd + 1, lvl + 1, verticalLines);
}

// Collects all vertical lines after DFS traversal and sorting by level
vector<vector<int>> verticalOrder(Node* root) {
    map<int, vector<pair<int,int>>> verticalLines;

    dfs(root, 0, 0, verticalLines);
    vector<vector<int>> res;

    for (auto& kv : verticalLines) {
        vector<pair<int,int>> lines = kv.second;

        // Sorting based on level
        stable_sort(lines.begin(), lines.end(), [](auto &a, auto &b) {
            return a.second < b.second;
        });

        vector<int> line;
        for (auto &node : lines) {
            line.push_back(node.first);
        }
        res.push_back(line);
    }

    return res;
}

int main() {
    // Create binary tree
    //            1
    //          /   \
    //         2     3
    //        / \   / \
    //       4   5  6   7
    //            \  \   \
    //             8  9   10
    //            /
    //           11
    
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->right->right = new Node(8);
    root->right->left->right = new Node(9);
    root->right->right->right = new Node(10);
    root->left->right->right->left = new Node(11);

    vector<vector<int>> res = verticalOrder(root);

    cout << "[";
    for (int i = 0; i < res.size(); i++) {
        cout << "[";
        vector<int> line = res[i];
        for (int j = 0; j < line.size(); j++) {
            cout << line[j];
            if (j != line.size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != res.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

Java

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;
import java.util.Collections;
import java.util.Comparator;

// Node Structure
class Node {
    int data;
    Node left, right;

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

class GFG {

    // Performs DFS to map each node to its horizontal distance and level
    static ArrayList<ArrayList<Integer>> verticalOrder(Node root) {
        TreeMap<Integer, ArrayList<ArrayList<Integer>>> map = new TreeMap<>();

        dfs(root, 0, 0, map);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();

        for (int hd : map.keySet()) {
            ArrayList<ArrayList<Integer>> lines = map.get(hd);

            // Sorting based on level (2nd element in list)
            Collections.sort(lines, Comparator.comparingInt(a -> a.get(1)));

            ArrayList<Integer> line = new ArrayList<>();
            for (ArrayList<Integer> node : lines) {
                
                // add only value, not level
                line.add(node.get(0)); 
            }
            res.add(line);
        }

        return res;
    }

    // Collects all vertical lines after DFS traversal and sorting by level
    static void dfs(Node root, int hd, int lvl, TreeMap<Integer, 
                    ArrayList<ArrayList<Integer>>> verticalLines) {
        
        if (root == null) return;

        ArrayList<ArrayList<Integer>> line = 
                    verticalLines.getOrDefault(hd, new ArrayList<>());

        // store node value and level as a small list
        ArrayList<Integer> nodeInfo = new ArrayList<>();
        nodeInfo.add(root.data);
        nodeInfo.add(lvl);
        line.add(nodeInfo);

        verticalLines.put(hd, line);

        // Recur for left and right subtrees
        dfs(root.left, hd - 1, lvl + 1, verticalLines);
        dfs(root.right, hd + 1, lvl + 1, verticalLines);
    }

    public static void main(String[] args) {

        // Create binary tree
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //       4   5 6   7
        //            \  \   \
        //             8  9   10
        //            /
        //           11

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.right = new Node(8);
        root.right.left.right = new Node(9);
        root.right.right.right = new Node(10);
        root.left.right.right.left = new Node(11);

        ArrayList<ArrayList<Integer>> res = verticalOrder(root);

        System.out.print("[");
        for (int i = 0; i < res.size(); i++) {
            System.out.print("[");
            List<Integer> line = res.get(i);
            for (int j = 0; j < line.size(); j++) {
                System.out.print(line.get(j));
                if (j != line.size() - 1) System.out.print(", ");
            }
            System.out.print("]");
            if (i != res.size() - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

Python

from collections import defaultdict

# Node Structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# Collects all vertical lines after DFS traversal and sorting by level
def verticalOrder(root):
    verticalLines = defaultdict(list)

    dfs(root, 0, 0, verticalLines)
    res = []

    for hd in sorted(verticalLines.keys()):
        lines = verticalLines[hd]

        # Sorting based on level
        lines.sort(key=lambda x: x[1])

        line = []
        for node in lines:
            line.append(node[0])
        res.append(line)

    return res

# Performs DFS to map each node to its horizontal distance and level
def dfs(root, hd, lvl, verticalLines):
    if root is None:
        return

    # storing node value and level
    verticalLines[hd].append((root.data, lvl))

    # Recur for left and right subtrees
    dfs(root.left, hd - 1, lvl + 1, verticalLines)
    dfs(root.right, hd + 1, lvl + 1, verticalLines)

if __name__ == "__main__":
    # Create binary tree
    #         1
    #       /   \
    #      2     3
    #     / \   / \
    #   4   5 6   7
    #         \  \   \
    #          8  9   10
    #         /
    #       11
    
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    root.left.right.right = Node(8)
    root.right.left.right = Node(9)
    root.right.right.right = Node(10)
    root.left.right.right.left = Node(11)

    res = verticalOrder(root)

    print("[", end="")
    for i in range(len(res)):
        print("[", end="")
        line = res[i]
        for j in range(len(line)):
            print(line[j], end="")
            if j != len(line) - 1:
                print(", ", end="")
        print("]", end="")
        if i != len(res) - 1:
            print(", ", end="")
    print("]")

C#

using System;
using System.Collections.Generic;
using System.Linq;

// Node Structure
class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = null;
        right = null;
    }
}

class GFG {
    
    // Collects all vertical lines after DFS traversal and sorting by level
    static List<List<int>> verticalOrder(Node root) {
        SortedDictionary<int, List<int[]>> map = new SortedDictionary<int, List<int[]>>();

        dfs(root, 0, 0, map);
        List<List<int>> res = new List<List<int>>();

        foreach (int hd in map.Keys) {
            List<int[]> lines = map[hd];

            // Sorting based on level
            lines = lines.OrderBy(a => a[1]).ToList();

            List<int> line = new List<int>();
            foreach (int[] node in lines) {
                line.Add(node[0]);
            }
            res.Add(line);
        }

        return res;
    }
    
    // Performs DFS to map each node to its horizontal distance and level
    static void dfs(Node root, int hd, int lvl, 
            SortedDictionary<int, List<int[]>> verticalLines) {
        if (root == null) return;

        if (!verticalLines.ContainsKey(hd))
            verticalLines[hd] = new List<int[]>();

        // storing node value and level
        verticalLines[hd].Add(new int[] { root.data, lvl });

        // Recur for left and right subtrees
        dfs(root.left, hd - 1, lvl + 1, verticalLines);
        dfs(root.right, hd + 1, lvl + 1, verticalLines);
    }

    static void Main(string[] args) {
        // Create binary tree
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //       4   5 6   7
        //            \  \   \
        //             8  9   10
        //            /
        //           11
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.right = new Node(8);
        root.right.left.right = new Node(9);
        root.right.right.right = new Node(10);
        root.left.right.right.left = new Node(11);

        List<List<int>> res = verticalOrder(root);

        Console.Write("[");
        for (int i = 0; i < res.Count; i++) {
            Console.Write("[");
            List<int> line = res[i];
            for (int j = 0; j < line.Count; j++) {
                Console.Write(line[j]);
                if (j != line.Count - 1) Console.Write(", ");
            }
            Console.Write("]");
            if (i != res.Count - 1) Console.Write(", ");
        }
        Console.WriteLine("]");
    }
}

JavaScript

// Node Structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Collects all vertical lines after DFS traversal and sorting by level
function verticalOrder(root) {
    let map = new Map();

    dfs(root, 0, 0, map);
    let res = [];

    let keys = Array.from(map.keys()).sort((a, b) => a - b);
    for (let hd of keys) {
        let lines = map.get(hd);

        // Sorting based on level
        lines.sort((a, b) => a[1] - b[1]);

        let line = [];
        for (let node of lines) {
            line.push(node[0]);
        }
        res.push(line);
    }

    return res;
}

// Performs DFS to map each node to its horizontal distance and level
function dfs(root, hd, lvl, verticalLines) {
    if (!root) return;

    let line = verticalLines.get(hd) || [];

    // storing node value and level
    line.push([root.data, lvl]);
    verticalLines.set(hd, line);

    // Recur for left and right subtrees
    dfs(root.left, hd - 1, lvl + 1, verticalLines);
    dfs(root.right, hd + 1, lvl + 1, verticalLines);
}

// Driver code

// Create binary tree
//            1
//          /   \
//         2     3
//        / \   / \
//       4   5 6   7
//            \  \   \
//             8  9   10
//            /
//           11
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.right.right = new Node(8);
root.right.left.right = new Node(9);
root.right.right.right = new Node(10);
root.left.right.right.left = new Node(11);

let res = verticalOrder(root);

process.stdout.write("[");
for (let i = 0; i < res.length; i++) {
    process.stdout.write("[");
    let line = res[i];
    for (let j = 0; j < line.length; j++) {
        process.stdout.write(line[j].toString());
        if (j != line.length - 1) process.stdout.write(", ");
    }
    process.stdout.write("]");
    if (i != res.length - 1) process.stdout.write(", ");
}
console.log("]");

Output

[[4], [2], [1, 5, 6, 11], [3, 8, 9], [7], [10]]

[Expected Approach] - Using BFS - O(n) Time and O(n) Space

In this approach, we are using map to store horizontal distance and nodes having that as horizontal distance from the root. BFS ensures that nodes are traversed in level order traversal. Therefore, we don't need any additional data structure in this approach to maintain level-order traversal.

C++

#include <iostream>
#include <vector>
#include <queue>   
#include <algorithm> 
#include <map>
#include <unordered_map>
using namespace std;

// Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = nullptr;
        right = nullptr;
    }
};

vector<vector<int>> verticalOrder(Node* root) {
    
    // Queue to store nodes and their vertical levels.
    unordered_map<int, vector<int>> lst;
    
    // Queue to store nodes and their vertical levels.
    queue<pair<Node *, int>> q;
    q.push({root, 0});
    
    int mn = 0, mx = 0;
    
    while (!q.empty()) {
        auto c = q.front();
        mn = min(mn, c.second);
        mx = max(mx, c.second);
        q.pop();
        
        // adding node to the corresponding vertical level.
        lst[c.second].push_back(c.first->data);
      
       // pushing left child with decreased vertical level.
        if (c.first->left)
            q.push({c.first->left, c.second - 1});
       
        // pushing right child with increased vertical level.
        if (c.first->right)
            q.push({c.first->right, c.second + 1});
    }
   
    // creating the result vector in vertical order.
    vector<vector<int>> res;
    for (int i = mn; i <= mx; i++)
        res.push_back(lst[i]);
  
    return res;
}

int main() {
    // Create binary tree
    //            1
    //          /   \
    //         2     3
    //        / \   / \
    //       4   5 6   7
    //            \  \   \
    //             8  9   10
    //            /
    //           11
    
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->right->right = new Node(8);
    root->right->left->right = new Node(9);
    root->right->right->right = new Node(10);
    root->left->right->right->left = new Node(11);

    vector<vector<int>> res = verticalOrder(root);

    cout << "[";
    for (int i = 0; i < res.size(); i++) {
        cout << "[";
        vector<int> line = res[i];
        for (int j = 0; j < line.size(); j++) {
            cout << line[j];
            if (j != line.size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != res.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

Java

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;

// Node Structure
class Node {
    int data;
    Node left, right;

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

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; }
}

class GFG {

    static ArrayList<ArrayList<Integer>> verticalOrder(Node root) {
        
        // Map to store nodes and their vertical levels.
        Map<Integer, ArrayList<Integer>> lst = new HashMap<>();
        
        // Queue to store nodes and their vertical levels.
        Queue<Pair<Node, Integer>> q = new LinkedList<>();
        q.offer(new Pair<>(root, 0));

        int mn = 0, mx = 0;

        while (!q.isEmpty()) {
            Pair<Node, Integer> c = q.poll();
            mn = Math.min(mn, c.getValue());
            mx = Math.max(mx, c.getValue());

            // adding node to the corresponding vertical level.
            lst.putIfAbsent(c.getValue(), new ArrayList<>());
            lst.get(c.getValue()).add(c.getKey().data);

            // pushing left child with decreased vertical level.
            if (c.getKey().left != null)
                q.offer(new Pair<>(c.getKey().left, c.getValue() - 1));

            // pushing right child with increased vertical level.
            if (c.getKey().right != null)
                q.offer(new Pair<>(c.getKey().right, c.getValue() + 1));
        }

        // creating the result vector in vertical order.
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int i = mn; i <= mx; i++)
            res.add(lst.get(i));

        return res;
    }

    public static void main(String[] args) {
        
        // Create binary tree
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //       4   5 6   7
        //            \  \   \
        //             8  9   10
        //            /
        //           11

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.right = new Node(8);
        root.right.left.right = new Node(9);
        root.right.right.right = new Node(10);
        root.left.right.right.left = new Node(11);

        ArrayList<ArrayList<Integer>> res = verticalOrder(root);

        System.out.print("[");
        for (int i = 0; i < res.size(); i++) {
            System.out.print("[");
            List<Integer> line = res.get(i);
            for (int j = 0; j < line.size(); j++) {
                System.out.print(line.get(j));
                if (j != line.size() - 1) System.out.print(", ");
            }
            System.out.print("]");
            if (i != res.size() - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

Python

from collections import deque, defaultdict

# Node Structure
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

def verticalOrder(root):
    if root is None:
        return []

    # Map to store nodes and their vertical levels.
    lst = defaultdict(list)

    # Queue to store nodes and their vertical levels.
    q = deque([(root, 0)])

    mn = 0
    mx = 0

    while q:
        node, val = q.popleft()
        mn = min(mn, val)
        mx = max(mx, val)

        # adding node to the corresponding vertical level.
        lst[val].append(node.data)

        # pushing left child with decreased vertical level.
        if node.left:
            q.append((node.left, val - 1))

        # pushing right child with increased vertical level.
        if node.right:
            q.append((node.right, val + 1))

    # creating the result vector in vertical order.
    res = []
    for i in range(mn, mx + 1):
        res.append(lst[i])

    return res


if __name__ == "__main__":
    
    # Create binary tree
    #            1
    #          /   \
    #         2     3
    #        / \   / \
    #       4   5 6   7
    #            \  \   \
    #             8  9   10
    #            /
    #           11
    
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.left = Node(6)
    root.right.right = Node(7)
    root.left.right.right = Node(8)
    root.right.left.right = Node(9)
    root.right.right.right = Node(10)
    root.left.right.right.left = Node(11)

    res = verticalOrder(root)

    print("[", end="")
    for i in range(len(res)):
        print("[", end="")
        line = res[i]
        for j in range(len(line)):
            print(line[j], end="")
            if j != len(line) - 1:
                print(", ", end="")
        print("]", end="")
        if i != len(res) - 1:
            print(", ", end="")
    print("]")

C#

using System;
using System.Collections.Generic;
using System.Linq;

// Node Structure
class Node {
    public int data;
    public Node left, right;

    public Node(int x) {
        data = x;
        left = right = null;
    }
}

class GFG {

    static List<List<int>> verticalOrder(Node root) {
        List<List<int>> res = new List<List<int>>();
        if (root == null) return res;

        // Map to store nodes and their vertical levels.
        Dictionary<int, List<int>> lst = new Dictionary<int, List<int>>();

        // Queue to store nodes and their vertical levels.
        Queue<(Node, int)> q = new Queue<(Node, int)>();
        q.Enqueue((root, 0));

        int mn = 0, mx = 0;

        while (q.Count > 0) {
            var curr = q.Dequeue();
            Node node = curr.Item1;
            int val = curr.Item2;

            mn = Math.Min(mn, val);
            mx = Math.Max(mx, val);

            // adding node to the corresponding vertical level.
            if (!lst.ContainsKey(val)) lst[val] = new List<int>();
            lst[val].Add(node.data);

            // pushing left child with decreased vertical level.
            if (node.left != null) q.Enqueue((node.left, val - 1));

            // pushing right child with increased vertical level.
            if (node.right != null) q.Enqueue((node.right, val + 1));
        }

        // creating the result vector in vertical order.
        for (int i = mn; i <= mx; i++)
            res.Add(lst[i]);

        return res;
    }

    static void Main(string[] args) {
      
        // Create binary tree
        //            1
        //          /   \
        //         2     3
        //        / \   / \
        //       4   5 6   7
        //            \  \   \
        //             8  9   10
        //            /
        //           11

        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.left.right.right = new Node(8);
        root.right.left.right = new Node(9);
        root.right.right.right = new Node(10);
        root.left.right.right.left = new Node(11);

        List<List<int>> res = verticalOrder(root);

        Console.Write("[");
        for (int i = 0; i < res.Count; i++) {
            Console.Write("[");
            List<int> line = res[i];
            for (int j = 0; j < line.Count; j++) {
                Console.Write(line[j]);
                if (j != line.Count - 1) Console.Write(", ");
            }
            Console.Write("]");
            if (i != res.Count - 1) Console.Write(", ");
        }
        Console.WriteLine("]");
    }
}

JavaScript

// Node Structure
class Node {
    constructor(x) {
        this.data = x;
        this.left = null;
        this.right = null;
    }
}

// Custom Queue Implementation
class Queue {
    constructor() {
        this.items = [];
        this.frontIndex = 0; 
    }

    enqueue(element) {
        this.items.push(element);
    }

    dequeue() {
        if (this.isEmpty()) return null;
        const item = this.items[this.frontIndex];
        this.frontIndex++;
        // Optional: Reset array if frontIndex gets large
        if (this.frontIndex > 1000) {
            this.items = this.items.slice(this.frontIndex);
            this.frontIndex = 0;
        }
        return item;
    }

    isEmpty() {
        return this.frontIndex >= this.items.length;
    }

    size() {
        return this.items.length - this.frontIndex;
    }
}

function verticalOrder(root) {
    if (!root) return [];

    // Map to store nodes and their vertical levels
    const lst = new Map();

    // Use our custom queue
    const q = new Queue();
    q.enqueue([root, 0]);

    let mn = 0, mx = 0;

    while (!q.isEmpty()) {
        const [node, val] = q.dequeue();

        mn = Math.min(mn, val);
        mx = Math.max(mx, val);

        if (!lst.has(val)) lst.set(val, []);
        lst.get(val).push(node.data);

        if (node.left) q.enqueue([node.left, val - 1]);
        if (node.right) q.enqueue([node.right, val + 1]);
    }

    // Build the result in vertical order
    const res = [];
    for (let i = mn; i <= mx; i++) {
        res.push(lst.get(i));
    }

    return res;
}

// Driver code
//            1
//          /   \
//         2     3
//        / \   / \
//       4   5 6   7
//            \  \   \
//             8  9   10
//            /
//           11
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.right.right = new Node(8);
root.right.left.right = new Node(9);
root.right.right.right = new Node(10);
root.left.right.right.left = new Node(11);

let res = verticalOrder(root);

// Display result
process.stdout.write("[");
for (let i = 0; i < res.length; i++) {
    process.stdout.write("[");
    let line = res[i];
    for (let j = 0; j < line.length; j++) {
        process.stdout.write(line[j].toString());
        if (j != line.length - 1) process.stdout.write(", ");
    }
    process.stdout.write("]");
    if (i != res.length - 1) process.stdout.write(", ");
}
console.log("]");

Output

[[4], [2], [1, 5, 6, 11], [3, 8, 9], [7], [10]]

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem