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
1 4
2 \
3 5
4 /
5 6The 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:
1class Node:
2 def __init__(self, val):
3 self.val = val
4 self.left = None
5 self.right = NoneFollow 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
-1000000000and1000000000 - Expected time complexity :
O(n) - Expected space complexity :
O(1)
xxxxxxxxxx76
def inorder(root): # fill in return root# Node definitionclass Node: def __init__(self, val): self.val = val self.left = None self.right = None# Regular binary treestree1 = Node(4)tree1.left = Node(1)tree1.right = Node(3)tree2 = Node(5)tree2.left = Node(10)tree2.left.left = Node(17)tree2.left.right = Node(3)tree2.right = Node(8)# Binary search treestree3 = Node(6)tree3.left = Node(3)OUTPUT
Results will appear here.