Binary Tree Vertical Order Traversal
MetaThe problem
Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column). If two nodes are in the same row and column, the order should be from left to right.
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanantion:
- Node 3 is at column 0, 9 is at column -1, and 20 is at column 1.
- 15 is at column 0 and 7 is at column 2. Sorting column-wise, we get [[9], [3,15], [20], [7]].
Input: root = [3,9,8,4,0,1,7] Output: [[4],[9],[3,0,1],[8],[7]] Explanantion: Nodes are assigned columns as follows:
- 3 at column 0, 9 at -1, 8 at 1.
- 4 at -2, 0 at 0, 1 at 0, 7 at 2. Sorting by column, the order is [[4], [9], [3,0,1], [8], [7]].
Input: root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6]
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
// Your code goes here
}
};java
/**
* 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 Solution {
public List<List<Integer>> verticalOrder(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.val = val
# self.left = left
# self.right = right
class Solution(object):
def verticalOrder(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[List[int]]
"""
# Your code goes herejavascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var verticalOrder = function(root) {
// Your code goes here
};csharp
public class Solution {
public IList<IList<int>> VerticalOrder(TreeNode root) {
//Your code goes here
}
}go
/*
Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
*/
func verticalOrder(root *TreeNode) [][]int {
}Stuck? Show a way to structure it+
- 01Queue pairs of node and column
- 02Append each dequeued value to its column bucket
- 03Enqueue left at column-1 then right at column+1
- 04Emit buckets from minimum to maximum column
Reference answer
Then expect these follow-ups
How does vertical traversal with row/value tie sorting differ?
Tests: follow-up reasoning
Can you avoid tracking min and max?
Tests: follow-up reasoning
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