Vertical Order Traversal of a Binary Tree

MEDIUM

Given a binary tree, return the vertical order traversal of its nodes’ values. For each node at position (X,Y), its left and right children respectively will be at positions (X-1, Y+1) and (X+1, Y+1). If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. The following example illustrates the vertical order traversal.

Example 1:

Binary Tree
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Explanation: 
We can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, 1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, 2);
The node with value 20 occurs at position (1, 1);
The node with value 7 occurs at position (2, 2).

The following figure is an illustration of the vertical order traversal.

Vertical Order Traversal of a Binary Tree

To find the location of every node, we can use a depth-first search. During the search, we will maintain the location (x, y) of the node. As we move from parent to child, the location changes to (x-1, y+1) or (x+1, y+1) depending on if it is a left child or right child. To report the locations, we sort them by x coordinate, then y coordinate, so that they are in the correct order to be added to our answer. At last, we will use a TreeMap to create the vertical order traversal.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class NodeLoc implements Comparable<NodeLoc> {
    int x;
    int y;
    TreeNode node;
 
    public NodeLoc(TreeNode node, int x, int y) {
        this.x = x;
        this.y = y;
        this.node = node;
    }
 
    public int compareTo(NodeLoc nl) {
        if (this.x != nl.x) return Integer.compare(this.x, nl.x);
        else if (this.y != nl.y) return Integer.compare(this.y, nl.y);
        else return Integer.compare(this.node.val, nl.node.val);
    }
}
 
class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
 
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Map<Integer, List<NodeLoc>> nodeByXCoordinate = new TreeMap<>();
        DFS(root, nodeByXCoordinate, 0, 0);
        for (Integer x : nodeByXCoordinate.keySet()) {
            List<NodeLoc> nodeLocList = nodeByXCoordinate.get(x);
            Collections.sort(nodeLocList);
            List<Integer> verticalLevel = new ArrayList<>();
            for (NodeLoc nodeLoc : nodeLocList) {
                verticalLevel.add(nodeLoc.node.val);
            }
            result.add(verticalLevel);
        }
        return result;
    }
 
    private void DFS(TreeNode node, Map<Integer, List<NodeLoc>> map, int x, int y) {
        if (node == null) {
            return;
        }
        List<NodeLoc> nodeLocList = map.get(x);
        if (nodeLocList == null) {
            nodeLocList = new ArrayList<>();
            map.put(x, nodeLocList);
        }
        NodeLoc nodeLoc = new NodeLoc(node, x, y);
        nodeLocList.add(nodeLoc);
        DFS(node.left, map, x - 1, y + 1);
        DFS(node.right, map, x + 1, y + 1);
    }
}

Complexity Analysis

  • Time Complexity: O(NlogN), where N is the number of nodes in the given tree.
  • Space Complexity: O(N).

Categories: Binary Tree, DFS

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s