Traversal is the key
Since we started we'll need to eventually return a merged root, let's go with an pre-order traversal. Pseudocode as follows:
xxxxxxxxxx
15
function preOrder(tree1, tree2) {
if (tree1 == null) {
return tree2;
}
if (tree2 == null) {
return tree1;
}
return tree1.val + tree2.val;
​
// Do the above on both of their left children
preOrder(tree1.left, tree2.left)
​
// Do the above on both of their right children
preOrder(tree1.right, tree2.right)
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment