Amazon Interview Question
SDE1sCountry: United States
Very similar to binary tree traversal but use an array of children as opposed to left and right. Complete solution in Python:
Recursive Solution in Python:
def preOrderRecursive(root):
res = []
def helper(root, res):
if not root:
return
res.append(root.val)
for child in root.children:
helper(child, res)
helper(root, res)
return res
Iterative Solution in Python:
def preOrderIterative(root):
st = []
st.append(root)
res = []
while len(st):
curr = st.pop()
res.append(curr.val)
for child in reversed(curr.children):
st.append(child)
return res
Test Code:
class Node:
def __init__(self, val):
self.val = val
self.children = []
'''
Construct the following tree:
1
/ | \
2 3 6
/\ \
4 5 7
'''
root = Node(1)
root.children = [Node(2), Node(3), Node(6)]
root.children[1].children = [Node(4), Node(5)]
root.children[2].children = [Node(7)]
print(preOrderRecursive(root)) # Output: [1, 2, 3, 4, 5, 6, 7]
print(preOrderIterative(root)) # Output: [1, 2, 3, 4, 5, 6, 7]
use stack to push root initially. Then iterate the stack until empty, pop out top and push child starting from right.
- vikalpveer March 31, 2018