Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Binary Tree Inorder Traversal (Main Thread)

Here is the interview question prompt, presented for reference.

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

  4
   \
    5
   /
  6

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:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
public class Node {
    int val;
    Node left;
    Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
struct Node {
  int val;
  Node* left = nullptr;
  Node* right = nullptr;

  Node(int val) : val(val) {}
};
public class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}
type Node struct {
    val   int
    left  *Node
    right *Node
}

func newNode(val int) *Node {
    return &Node{val, nil, nil}
}

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)

You can see the full challenge with visuals at this link.

Challenges • Asked over 4 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Jul 09, 2019:

This is the main discussion thread generated for Binary Tree Inorder Traversal.

Jake from AlgoDaily Commented on Jul 09, 2019:

Hey @mattvanwinkle:disqus, I went through and double checked all of the tests for tree questions. They should be fine now after a hard refresh and clicking "RESET".

Thanks for being on top of this!

Anonymous Commented on Apr 05, 2020:

I think the BST shown is incorrect.
```
4
\
5
/
6

SNIPPET
This tree violates the condition that a left child should be less than its parent. I think the tree should look like this:

4
\
6
/
5
``
Then the in order traversal woud be:
[4, 5, 6]`

Anonymous Commented on Aug 06, 2020:

The Python skeleton code, line 3 should be "self.val = v" rather than "self.v = v"

Jake from AlgoDaily Commented on Aug 06, 2020:

I believe you're referring to the first Python community solution. That was a new Node class defined by one of our users, and it works because it's self-defined and doesn't rely on our definition.

Jake from AlgoDaily Commented on Aug 06, 2020:

This problem is for any binary tree, not necessarily just binary search trees.

Anonymous Commented on Aug 12, 2020:

Shouldn't the Postorder traversal be left-right-root? Currently, it shows the same ordering as In-Order.

Jake from AlgoDaily Commented on Aug 24, 2020:

Thank you! Fixed.