How to check if two binary trees are the same

Given two binary trees, write a method to check if the trees are the same or not.

Example

Output: False, these trees are different because their left nodes have different values

/* Definition for TreeNode
public class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
    }
}
*/

public sealed class Solution
{
    public bool IsSameTree(TreeNode one, TreeNode two)
    {
    }
}

Algorithm

Before writing a code let's think what does it mean same trees. From the binary tree article, we already know - a binary tree is a hierarchical data structure with left and right subtrees. So, the trees are the same if root values are the same and left and right subtrees are the same too. We can compare trees recursively using one of the tree traversals

Code

public bool IsSameTree(TreeNode one, TreeNode two)
{
    if (one == null && two == null)
    {
        return true;
    }

    if (one == null || two == null)
    {
        return false;
    }

    if (one.Value == two.Value)
    {
        return IsSameTree(one.Left, two.Left) && IsSameTree(one.Right, two.Right);
    }

    return false;
}

Video Lesson