Leaf-Similar Trees

easy tree dfs

Problem

Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence. For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8). Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Inputt1 = [3,5,1,6,2,9,8], t2 = [3,5,1,6,7,4,2,_,_,_,_,_,_,9,8]

Outputtrue / false depending on layout

Leaves are read in order during DFS — try both inputs in the visualizer.

tree A (level-order, '_' for null)

tree B

def leaves(root):
    out = []
    def dfs(n):
        if not n: return
        if not n.left and not n.right:
            out.append(n.val); return
        dfs(n.left); dfs(n.right)
    dfs(root); return out
def leaf_similar(a, b):
    return leaves(a) == leaves(b)

function leaves(root) {
  const out = [];
  function dfs(n) {
    if (!n) return;
    if (!n.left && !n.right) { out.push(n.val); return; }
    dfs(n.left); dfs(n.right);
  }
  dfs(root); return out;
}
function leafSimilar(a, b) {
  const x = leaves(a), y = leaves(b);
  return x.length === y.length && x.every((v, i) => v === y[i]);
}

class Solution {
    public boolean leafSimilar(TreeNode a, TreeNode b) {
        List<Integer> la = new ArrayList<>(), lb = new ArrayList<>();
        leaves(a, la); leaves(b, lb);
        return la.equals(lb);
    }
    private void leaves(TreeNode n, List<Integer> out) {
        if (n == null) return;
        if (n.left == null && n.right == null) { out.add(n.val); return; }
        leaves(n.left, out); leaves(n.right, out);
    }
}

void leaves(TreeNode* n, vector<int>& out) {
    if (!n) return;
    if (!n->left && !n->right) { out.push_back(n->val); return; }
    leaves(n->left, out); leaves(n->right, out);
}
bool leafSimilar(TreeNode* a, TreeNode* b) {
    vector<int> la, lb;
    leaves(a, la); leaves(b, lb);
    return la == lb;
}

Explanation

Two trees are leaf-similar if their leaves, read left to right, spell out the same sequence. The straightforward plan is to collect each tree's leaf sequence and then compare the two lists.

To gather the leaves in the right order we run a DFS that always visits the left child before the right. A node is a leaf when it has no children, and only then do we append its value. Internal nodes contribute nothing themselves; they just route the walk.

Because DFS goes left-first, the leaves get appended in exactly the left-to-right order the problem asks for. We do this for both trees, producing leaves(a) and leaves(b).

Finally we check that the two sequences are equal element by element. If they match, the trees are leaf-similar; otherwise they are not.

Example: a tree whose leaves come out as [6, 2, 9, 8] is leaf-similar to any other tree that also yields [6, 2, 9, 8], regardless of internal shape. Each tree is walked once, so the cost is O(|a| + |b|).

Time: O(|a| + |b|) Space: O(h) recursion