## Amazon Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

use stack to push root initially. Then iterate the stack until empty, pop out top and push child starting from right.

``````void preOrder(Node *root) {

std::stack<Node *> S;
S.push(root);

while(!S.empty()) {
Node *temp = S.top();
S.pop();
std::cout << temp->val << " ";
for(int i = temp->child.size(); I >=0; i--) {
if(temp->child[i]
S.push(temp->child[I];
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.