# Custom Tree Traversal

2 min read Tweet this post

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``````
Section titled Solution

## Solution

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

### 1. Breadth-first search (BFS) using a queue:

• 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.
Section titled 2.%20Depth-first%20search%20%28DFS%29%20using%20a%20stack%3A

### 2. Depth-first search (DFS) using a stack:

• 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.
Section titled 3.%20Morris%20traversal%3A

### 3. Morris traversal:

• 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>

``````//
// 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>

go data-structure tree