Custom Tree Traversal

In the previous post you knew about basic of the tree data structure. Now we are focusing on how to some use rules below

Note: The goals is using iterative approach

Given a binary tree of integers t, return its node values in the following format:

The first element should be the value of the tree root; The next elements should be the values of the nodes at height 1 (i.e. the root children), ordered from the leftmost to the rightmost one; The elements after that should be the values of the nodes at height 2 (i.e. the children of the nodes at height 1) ordered in the same way; Etc.

For

t = {
    "value": 1,
    "left": {
        "value": 2,
        "left": null,
        "right": {
            "value": 3,
            "left": null,
            "right": null
        }
    },
    "right": {
        "value": 4,
        "left": {
            "value": 5,
            "left": null,
            "right": null
        },
        "right": null
    }
}

the output should be
solution(t) = [1, 2, 4, 3, 5].

This t looks like this:

     1
   /   \
  2     4
   \   /
    3 5

There are several ways to traverse a binary tree without using recursion, including:

• Start by enqueuing the root node of the tree.
• Dequeue a node from the queue and visit it.
• Enqueue the left and right children of the dequeued node.
• Repeat steps 2 and 3 until the queue is empty.

• Start by pushing the root node of the tree onto the stack.
• Pop a node from the stack and visit it.
• Push the right and left children of the popped node onto the stack.
• Repeat steps 2 and 3 until the stack is empty.

• Initialize current node as root
• While current node is not NULL,
  • If current node doesn’t have left child, visit it and move to its right
  • If current node has a left child, inorder predecessor is the rightmost node in the left subtree or the left child. Make current as right child of the rightmost node in the left subtree and move current to left child.

• Use a stack to keep track of the current node and its ancestors as you traverse down the tree.
• When you reach a leaf or a node with no right child, backtrack to the nearest ancestor that has a right child that you haven’t yet visited, and then visit that right child.

All these methods allow you to traverse the binary tree without using recursion, but they each have their own specific use cases and trade-offs.

For this article I will focus on the simplest one using BFS

<CH.Section>

• Handle if the root is empty, return empty array of integers
• Initialize the queue with the root of the tree and prepare slice for hold the return values
• Iterate process until the queue is empty
• Get first element from queue
• Dequeue the queue
• Append the pop value into result slice
• If pop has left or right node append to queue

//
// Binary trees are already defined with this interface:
// type Tree struct {
//   Value interface{}
//   Left *Tree
//   Right *Tree
// }
func solution(t *Tree) []int {
    if t==nil{
        return []int{}
    }

    result:=[]int{}
    queue:=[]*Tree{t}

    for len(queue)>0{
        pop := queue[0]  // pop queue
        queue=queue[1:]  // dequeue

        result = append(result, pop.Value.(int))

        if pop.Left!=nil{
            queue = append(queue, pop.Left)
        }

        if pop.Right !=nil{
            queue = append(queue, pop.Right)
        }
    }

    return result
}

</CH.Section>