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:

1public class Node {
2    int val;
3    Node left;
4    Node right;
5
6    public Node(int val) {
7        this.val = val;
8        this.left = null;
9        this.right = null;
10    }
11}

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
​
 
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.JUnitCore;
import org.junit.runner.Result;
import org.junit.runner.notification.Failure;
​
import static org.junit.jupiter.api.Assertions.assertIterableEquals;
​
import java.util.Arrays;
​
// solution
​
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
​
class Solution {
    public static List<Integer> inorderTraversal(Node root) {
        // fill in
        // with solution
        return new ArrayList<Integer>();
    }
​
    // print your findings using this function!
    public static void log() {
        System.out.println(inorderTraversal(null));
    }

OUTPUT

Results will appear here.