One Pager Cheat Sheet

• The sum of overlapping nodes is used to create the merged tree, while nodes that do not overlap remain unchanged, within the constraints of O(m+n) time complexity and -1000000000 to 1000000000 for node values.
• We can merge trees with just root nodes to gauge how we'd perform this exercise for trees with children.
• We can brute force solve a problem by visualizing how a human would do it, and running through examples to find patterns.
• The merge rule states that when two nodes overlap, their attributes and properties are combined summarily to form a resultant node.
• The merge rule allows any two overlapping nodes to be combined, so it does not have to start from the root nodes of both trees.
• We could sum up the node values of two trees, by processing at the root of each one, and then checking for left and right children, according to rule #2.
• We scan the tree from left to right and sum up the values we find between each node, returning 4 from the root's left child.
• The merge tree function combines the two tree nodes by adding the two elements within them together to get the result.
• The algorithm of pre-order traversal is a Depth-First Search which visits the nodes of a tree in the root, left, right order.
• We can traverse both trees simultaneously and check their values at each step to create a pattern.
• The pre-order traversal technique is the key to returning a merged root.
• Checking the node position of the currently investigated element at the first and second trees using doSomeOperation() can determine what to return.
• We should merge the two nodes by adding their values onto the first tree, and then simply return it.
• The process of merging two binary trees recursively begins with a pre-order traversal of the first tree, checking the nodes of both trees, and then updating the first tree with the sum of their values before continuing with the subtrees.
• We should traverse both trees before returning tree1, writing the merge results in the process.
• We traverse through both binary trees at once with a time complexity of O(m+n), allowing us to process one node of each tree per iteration.
• The time complexity of the recursive tree merger algorithm is O(n), as it only traverses the larger tree, resulting in a worst-case of O(n) nodes.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function Node(val) {

  this.val = val;

  this.left = this.right = null;

}

​

function mergeTwoBinaryTrees(tree1, tree2) {

  if (tree1 == null) {

    return tree2;

  }

  if (tree2 == null) {

    return tree1;

  }

  tree1.val += tree2.val;

  tree1.left = mergeTwoBinaryTrees(tree1.left, tree2.left);

  tree1.right = mergeTwoBinaryTrees(tree1.right, tree2.right);

  return tree1;

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.