Tree Traversal Algorithm: How do you traverse a binary tree in-order (recursively and iteratively)? What are its use cases?
Assume:
class TreeNode:
def __init__(self, val):
self.val = val
self.right = None
self.left = None
Iterative
def inorder_iterative(node):
res = []
if not node:
return res
stack = []
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val) # additional logic here!
node = node.right
return res
Recursive
def inorder_recursive(node, res=None):
if node is None:
return []
if res is None:
res = []
inorder_recursive(node.left, res)
res.append(node.val) # additional logic here!
inorder_recursive(node.right, res)
return res