Decode the Coding Interview in Go: Real-World Examples/

...

/

Binary Tree Vertical Order Traversal

Binary Tree Vertical Order Traversal

Understand and solve the interview question "Binary Tree Vertical Order Traversal".

We'll cover the following...

Description

The goal is to find the binary tree vertical order traversal of the binary tree when the root of this binary tree is given. In other words, you have to return the values of the nodes from top to bottom in each column, column by column from left to right. If there is more than one node in the same column and row, return the values from left to right. Let’s go over some examples:

Coding exercise

package main
import (
  "fmt"
  "strconv"
  "encoding/json"
)
type TreeNode struct{
    val int
    left *TreeNode
    right *TreeNode
}
func verticalOrder(root *TreeNode) [][]int {
    // write your code here
    return [][]int{}
}
Binary Tree Vertical Order Traversal

Solution

The solution we will implement follows a breadth-first search. The intuition behind BFS is that it guarantees that nodes at the top will be visited first and the nodes at the bottom will be visited last. As for the traversal of the tree from left to right, we need to maintain a HashMap that contains the list of all the nodes in a specific column. We will denote these columns by their index, where the column of the root will be index 0, the columns on the left side of the root will have a negative index, and the columns on the right side of the root will have a positive index. The index of each column will be a key.

We also need to store the value of the minimum and maximum indexes in two variables, so we can iterate over the indices to get the nodes in the right order.

Let’s go over the algorithm in detail:

  1. We need to create a HashMap called nodesList in which the key will be the index of the column and the value will be the list of nodes in that column.

  2. We initialize two variables to store the minimum and maximum values of the index.

  3. During BFS, we also maintain a queue to keep track of the order of nodes that need to be visited. We will initialize the queue ...

Access this course and 1400+ top-rated courses and projects.