Same Binary Tree

NeetCode: Same Binary Tree · LeetCode: 100. Same Binary Tree · Difficulty: Easy

Return true if two binary trees have the same structure and the same values at every position.

Example

Text

Input:  [1, 2, 3] and [1, 2, 3]    Output: true
Input:  [1, 2, 3] and [1, 3, 2]    Output: false

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed.

Brute force: serialize both and compare strings

A preorder listing that also writes N for missing children identifies a tree uniquely, so two trees are equal exactly when their listings are equal. The listing is built with a StringBuilder, and the strings are compared with equals, not == (which would compare references).

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return serialize(p).equals(serialize(q));
    }

    private String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        write(root, sb);
        return sb.toString();
    }

    private void write(TreeNode node, StringBuilder sb) {
        if (sb.length() > 0) sb.append(',');
        if (node == null) {
            sb.append('N');
            return;
        }
        sb.append(node.val);
        write(node.left, sb);
        write(node.right, sb);
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isSameTree(tree(1, 2, 3), tree(1, 2, 3)));
        System.out.println(new Solution().isSameTree(tree(1, 2, 3), tree(1, 3, 2)));
    }
}

Output

true
false

Time: O(n). Space: O(n) for the strings.

Optimal: compare node by node

Walk both trees together. Two empty subtrees match, one empty and one non-empty do not, and two real nodes match if their values are equal and both child pairs match. The comparison stops at the first difference, and no strings are built.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().isSameTree(tree(1, 2, 3), tree(1, 2, 3)));
        System.out.println(new Solution().isSameTree(tree(1, 2, 3), tree(1, 3, 2)));
        System.out.println(new Solution().isSameTree(tree(), tree()));
    }
}

Output

true
false
true

p.val == q.val compares two int fields, so == is correct here. Time: O(n), and often much less because it exits early. Space: O(h).