Vertical Order Traversal
SalesforceThe problem
Compute the binary tree's vertical order traversal given its root. The left and right children of a node at location (row, col) will be at (row + 1, col - 1) and (row + 1, col + 1), respectively. The tree's root is located at (0, 0).
The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values. Return the binary tree's vertical order traversal.
Input : root = [3, 9, 20, null, null, 15, 7] Output : [ [9] , [3, 15] , [20] , [7] ] Explanation : Column -1: Only node 9 is in this column. Column 0: Nodes 3 and 15 are in this column in that order from top to bottom. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.
Input : root = [1, 2, 3, 4, 5, 6, 7] Output : [ [4] , [2] , [1, 5, 6] , [3] , [7] ] Explanation : Column -2: Only node 4 is in this column. Column -1: Only node 2 is in this column. Column 0: Nodes 1, 5, and 6 are in this column.1 is at the top, so it comes first. 5 and 6 are at the same position (2, 0), so we sort them by their value, 5 before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.
Input : root = [5, 1, 2, 8, null, 4, 5, null, 6]
- 1 <= Number of Nodes <= 104
- -103 <= Node.val <= 103
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
vector<vector<int> > verticalTraversal(TreeNode* root) {
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.data = val
# self.left = left
# self.right = right
class Solution:
def verticalTraversal(self, root):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
verticalTraversal(root) {
//your code goes here
}
}csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution
{
public IList<IList<int>> VerticalTraversal(TreeNode root)
{
//your code goes here
}
}go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Data int
* Left *TreeNode
* Right *TreeNode
* }
*/
func verticalTraversal(root *TreeNode) [][]int {
}Stuck? Show a way to structure it+
- 01Assign each node row and column coordinates.
- 02Collect triples by column, row, and value.
- 03Sort by column then row then value.
- 04Group equal columns into the output.
Reference answer
Then expect these follow-ups
How does ordinary vertical order differ?
Tests: spec distinction
Can ordered maps reduce explicit sorting?
Tests: data structures
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question