First pair non matching leaves

http://shirleyisnotageek.blogspot.com/2016/11/first-pair-non-matching-leaves.html

Given two (binary) trees, return the first pair of non-matching leaves

Tree 1: A, B, C, D, E, null, null
Tree 2: A, D, B

Output: (E,B)

DFS, but be smart on how to get the leaves. The idea is whenever we find two leaves when we traverse the two trees, we compare if there are not equal, if they are, return them, otherwise keep traversing until we find the result. 

   public int[] firstPairNoMatchingNodes (TreeNode r1, TreeNode r2) {

        if (r1 == null || r2 == null) {

            return new int[]{-1, -1};

        }

        Stack<TreeNode> tree1 = new Stack<>();

        Stack<TreeNode> tree2 = new Stack<>();

        getLeaves(r1, tree1);

        getLeaves(r2, tree2);

 

        TreeNode leaf1 = getLeaf(tree1);

        TreeNode leaf2 = getLeaf(tree2);

        while (leaf1 != null && leaf2 != null) {

            if (leaf1.val != leaf2.val) {

                return new int[]{leaf1.val, leaf2.val};

            }

            leaf1 = getLeaf(tree1);

            leaf2 = getLeaf(tree2);

        }

        return new int[]{-1, -1};

    }

 

    private void getLeaves(TreeNode root, Stack<treenode> stack) {

        while (root != null) {

            stack.add(root);

            root = root.left;

        }

    }

 

    private TreeNode getLeaf(Stack<treenode> tree) {

        while (!tree.isEmpty()) {

            TreeNode curr = tree.pop();

            if (curr.left == null && curr.right == null) {

                return curr;

            } else if (curr.right != null) {

               getLeaves(curr.right, tree);

            }

        }

        return null;

    }