Algorithm problem: Check if two binary tree are same

Tree is a common data structure that is often asked during technical interview problems, and one of most commonly asked easy problems is the following:

PROBLEM STATEMENT: Same binary trees

Given the roots of two binary trees p and q, return true if the trees are equivalent, otherwise return false.

Two binary trees are considered equivalent if they share the exact same structure and the nodes have the same values.

How to check if two binary trees are same?

And for a Java function, the function may look like this:

 /**
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 **/
public boolean isSameTree(TreeNode p, TreeNode q) {
  // CODES
  
}

There are multiple ways to solve it, but all of them pretty much require to traverse through Depth First Search (DFS) or Breadth First Search (BFS).

To solve it recursively, we need to understand the base condition. In our case, that is when p = null and q = null . This is because nodes will eventually have to reach null (unless it is cyclic).