Same Leaf Sequence

easy tree dfs

Problem

Two binary trees have the same leaf sequence if a left-to-right DFS reads the same list of leaf values from each. Collect each tree's leaves in order and compare.

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 same_leaf_seq(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 sameLeafSeq(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 sameLeafSeq(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 sameLeafSeq(TreeNode* a, TreeNode* b) {
    vector<int> la, lb;
    leaves(a, la); leaves(b, lb);
    return la == lb;
}

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