AlgoDaily - Binary Tree Inorder Traversal

Binary Tree Inorder Traversal (Easy)

Good morning! Here's our prompt for today.

You may see this problem at Flipkart, Slack, Netflix, Snap, Checkout Com, Digitate, Pagerduty, Seagate, Elastic, Anaplan, and Dell.

Can you write a function to traverse a binary tree in-order, and print out the value of each node as it passes?

SNIPPET

The example would output [4, 6, 5] since there is no left child for 4, and 6 is visited in-order before 5.

The definition of a tree node is as follows:

1type Node struct {
2    val   int
3    left  *Node
4    right *Node
5}
6
7func newNode(val int) *Node {
8    return &Node{val, nil, nil}
9}

Follow up: you'll likely get the recursive solution first, could you do it iteratively?

Constraints

Number of vertices in the tree <= 100000
The values of the vertices in the tree will be between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(1)

xxxxxxxxxx
​
 
package main
​
import (
  "fmt"
  "reflect"
)
​
type Node struct {
  val   int
  left  *Node
  right *Node
}
​
func InorderTraversal(root *Node) []int {
  //fill in this function
  return []int{}
}
​
func main() {
  /*
        10
         /  \
       20    30
      / \      \
       40  50     60
      /
     70

OUTPUT

Results will appear here.