DEV Community

Virendra Jadhav
Virendra Jadhav

Posted on

🌳 Vertical Order Traversal of a Binary Tree – Explained with Java, Python, and C++ Solutions

#dsa #java #python #cpp

title: "Vertical Order Traversal of a Binary Tree: Explained with Java, Python, and C++" description: "A complete guide to solving the Vertical Order Traversal problem with visual explanations and solutions in Java, Python, and C++." tags: ["dsa", "leetcode", "binary-tree", "java", "python", "cpp", "algorithms"]

🌳 Vertical Order Traversal of a Binary Tree – Explained with Java, Python, and C++ Solutions

By Virendra Jadhav

When working with binary trees, we usually traverse them in pre-order, in-order, post-order, or level-order.\
But vertical order traversal introduces a new dimension — literally. Instead of going top to bottom or left to right, we explore the tree column by column.

In this post, you’ll learn:

  • ✅ What vertical order traversal is
  • ✅ A step-by-step breakdown with a visual example
  • ✅ Java, Python, and C++ solutions
  • ✅ Related problems to build deeper tree traversal skills

🔍 Problem Understanding

Given the root of a binary tree, we need to return the vertical order traversal of its nodes' values.

👇 Visual Example: 

       3
     /   \
    9     20
         /  \
        15   7
Enter fullscreen mode Exit fullscreen mode

xpected Output:

[
  [9],
  [3, 15],
  [20],
  [7]
]
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • The leftmost vertical line contains node 9.
  • The next vertical line contains nodes 3 and 15.
  • The next contains node 20.
  • The rightmost vertical line contains node 7.

💡 Intuition

To solve this, we need to:

  • Track each node’s vertical index (horizontal distance from the root).
  • Traverse the tree using DFS while keeping track of the current level and vertical index.
  • Use a TreeMap to automatically sort the vertical indices.
  • At each vertical index, sort nodes by their level and then by value.

🚀 Approach

Key Ideas:

  • Use a nested TreeMap: 
  TreeMap<VerticalIndex, TreeMap<Level, PriorityQueue<NodeValues>>>
Enter fullscreen mode Exit fullscreen mode
  • Store nodes in a min-heap (PriorityQueue) to handle tie-breakers when nodes share the same position.
  • Traverse using a helper function that carries level and verticalIndex.

✅ Java Solution 

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

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

        for (TreeMap<Integer, PriorityQueue<Integer>> levels : map.values()) {
            List<Integer> vertical = new ArrayList<>();
            for (PriorityQueue<Integer> nodes : levels.values()) {
                while (!nodes.isEmpty()) {
                    vertical.add(nodes.poll());
                }
            }
            result.add(vertical);
        }

        return result;
    }

    private void traverse(TreeNode node, TreeMap<Integer, TreeMap<Integer, PriorityQueue<Integer>>> map, int level, int verticalIndex) {
        if (node == null) return;

        map.putIfAbsent(verticalIndex, new TreeMap<>());
        map.get(verticalIndex).putIfAbsent(level, new PriorityQueue<>());
        map.get(verticalIndex).get(level).offer(node.val);

        traverse(node.left, map, level + 1, verticalIndex - 1);
        traverse(node.right, map, level + 1, verticalIndex + 1);
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Python Solution 

from collections import defaultdict, deque

class Solution:
    def verticalTraversal(self, root):
        node_map = defaultdict(lambda: defaultdict(list))
        queue = deque([(root, 0, 0)])

        while queue:
            node, verticalIndex, level = queue.popleft()
            if node:
                node_map[verticalIndex][level].append(node.val)
                queue.append((node.left, verticalIndex - 1, level + 1))
                queue.append((node.right, verticalIndex + 1, level + 1))

        result = []
        for x in sorted(node_map.keys()):
            vertical = []
            for y in sorted(node_map[x].keys()):
                vertical.extend(sorted(node_map[x][y]))
            result.append(vertical)

        return result
Enter fullscreen mode Exit fullscreen mode

✅ C++ Solution 

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        map<int, map<int, multiset<int>>> nodes;
        queue<tuple<TreeNode*, int, int>> q;

        q.push({root, 0, 0});

        while (!q.empty()) {
            auto [node, verticalIndex, level] = q.front();
            q.pop();

            if (node) {
                nodes[verticalIndex][level].insert(node->val);
                q.push({node->left, verticalIndex - 1, level + 1});
                q.push({node->right, verticalIndex + 1, level + 1});
            }
        }

        vector<vector<int>> result;
        for (auto &[x, y_map] : nodes) {
            vector<int> vertical;
            for (auto &[y, node_set] : y_map) {
                vertical.insert(vertical.end(), node_set.begin(), node_set.end());
            }
            result.push_back(vertical);
        }

        return result;
    }
};
Enter fullscreen mode Exit fullscreen mode

🕒 Complexity

  • Time Complexity: O(N log N)\
    Sorting and TreeMap operations dominate.

  • Space Complexity: O(N)\
    All nodes are stored in maps.

🔗 Related LeetCode Problems

👌 Final Thoughts

Vertical Order Traversal is a perfect example of using smart data structures like TreeMap and PriorityQueue to solve complex traversal problems in trees.

If you found this helpful, let's connect and explore more challenging DSA problems together!

Top comments (0)