Today I’m looking at the next Leetcode July Challenge problem, Same Tree. This problem presents us with the roots of two binary trees and asks us to return whether the two trees are the same, where sameness reflects an identical tree structure as well as identical node values between the two trees. A couple of algorithms immediately come to mind, primarily depth-first and breadth-first search. The tricky bit will be to make sure we’re searching the two trees simultaneously. My initial instinct is typically not to reach for a recursive algorithm, but the recursive dfs in this instance is very simple, so we’ll start there before moving on to an iterative approach.

bool isSameTreeRecursiveDFS(TreeNode* a, TreeNode* b) {
   if(!a || !b) return !a && !b;
   return a->val == b->val 
	  && isSameTree(a->left, b->left) 
	  && isSameTree(a->right, b->right);
}

Simple, concise, and useful. That’s what recursion is good at! That quick work is useful for clearly writing out the base cases for sameness in this problem:

  1. If either node is null, they should both be null.
  2. If neither node is null, their values should be equal.

Great, now we can write the typical iterative depth-first and breadth-first algorithms and plug in those base case checks. We’ll handle keeping the two trees in sync similarly to how the recursive algorithm does, by pushing the nodes to our data structure as a pair.

// Breadth-first search
bool isSameTreeBFS(TreeNode* a, TreeNode* b) {
   queue<pair<TreeNode*,TreeNode*>> q;
   q.push({a, b});
   
   while(!q.empty()) {
	  auto [aNode, bNode] = q.front();
	  q.pop();
	 
	  // the exclusive or: returns true if aNode is null and bNode isn't, or vice versa.
	  if(!aNode ^ !bNode) return false;
	  if(aNode && bNode) {
		 if(aNode->val != bNode->val) return false;
		 q.push({aNode->left, bNode->left});
		 q.push({aNode->right, bNode->right});
	  }  
   }
   return true;
}
// Depth-first search
bool isSameTreeDFS(TreeNode* a, TreeNode* b) {
   stack<pair<TreeNode*,TreeNode*>> s;
   s.push({a, b});
   
   while(!s.empty()) {
	  auto [aNode, bNode] = s.top();
	  s.pop();
	  
	  if(!aNode ^ !bNode) return false;
	  if(aNode && bNode) {
		 if(aNode->val != bNode->val) return false;
		 s.push({aNode->left, bNode->left});
		 s.push({aNode->right, bNode->right});
	  }  
   }
   return true;
}

This is a really great example of how easy it is to switch between the iterative dfs and bfs based entirely on the data structure we use. The choice between the two would be based largely around knowing some typical input patterns for optimizations of memory use. The breadth-first algorithm will have its worst case memory performance with a full binary tree requiring N/2, O(N), space and its best case performance for a completely unbalanced tree. This opposite is true for the stack-based depth-first search which will have its best case performance for a full binary tree requiring log N space, and its worst case memory performance, O(n), for a completely unbalanced tree. That was a great opportunity to get a clean look at those two important algorithms.