Facebook Interview Question for

Catherine

You can solve this using a stack and a root value.


You initialize the root as Integer.MIN_VALUE

for each number:
if number less than root -> return false;

if number greater than root -> pop stack until the peek value of the stack is greater than the number, make the last popped value the root, the other popped values are the leafes

push the number on the stack

Ursula@CA

With BST pre-order array, leaf node seems to be the element that smaller than next element. Is this assumption correct? If so, we can use this to write two loops for each of the array.

透明

From a pre-order traversal array of a BST, we can detect leaves by doing a sequential scan of the array with a helper stack (see code below for finding the next leaf).
From there, we can just keep on finding the next leaf in each tree and compare until we find leaves that don't match (or we run out of leaves in one tree before the other; or we just find no mismatches). 9 h! ]: G& H6 ?" ?' v+ _
# Z5 J1 b; ~: L Q
A binary tree with pre-order traversal array of 1,2,3 can be a root of 1 with left child 2 and right child 3, or it could be a linked list (e.g. 1 with right child 2, and 2 with right child 3)

Runtime: O(n). Space complexity: O(log n)

static int? NextLeaf(int[] preOrderTraversal, int offset, Stack<int> stack)
  b, L* }$ x0 c: [( f8 p% [0 Y. A( ]        {
            if (offset == preOrderTraversal.Length - 1)
9 x  b! H$ R; `; x( m' p            {
                return offset;
            }
6 Z- N8 e! J2 x4 e
: _# G4 {( Z( P! L+ ]4 z: n/ J: [            if (offset > preOrderTraversal.Length - 1)
% i- r7 R% U6 j+ j, p# z' M3 e            {
                return null;
' @* \8 B$ @( Y            }

            var current = preOrderTraversal[offset];
! g+ K5 p. Q$ K+ k# h            var next = preOrderTraversal[offset + 1];
' i9 [8 F; v5 U/ w* P5 {: E
; K4 w0 _: Z4 p8 e* d            // Next is smaller? Then it is the left sub-tree root
6 F  e  G* k, |( ]6 Z) S            // Next item is bigger. Is it bigger than my ancestor?
, m9 q% M& y; u- C9 Q$ S            // No - then current is the parent, and the next item is the root of the right sub-tree
% J0 S7 S' V& p" f5 }            // Yes - then current is a leaf. Pop ancestors until you get to the common ancestor (and pop that one too)
- J- ]  M: h! X            if (current > next || stack.Count == 0 || next < stack.Peek())
/ C! F4 t- B' u, i# o4 `0 R            {
                stack.Push(current);
" g) o$ X' t! |                return NextLeaf(preOrderTraversal, offset + 1, stack);
& ?5 l  P% u& q4 a8 V            }
' Z, L  w0 c# ]2 A: K$ ]
7 G0 [6 f" y6 ^7 X) d9 q3 c3 b  p            // The stack is empty, or the next is not bigger than the immediate ancestor. 
            while (stack.Count > 0 && stack.Peek() < next) stack.Pop();
* {: ~; {! {- E6 }! n  J0 I            return offset;
1 y2 V% E6 I$ E: ^& c6 Z% N        }
/ K- I; Y6 h4 L- f& m) l3 @, m
            if (preOrderTraversal1.Length == 0 || preOrderTraversal2.Length == 0)
- r3 N2 p( G- t* Q& X+ Y            {
                return;
2 n) A' G. M" L            }

            var iStack = new Stack<int>();
. P8 u: E; v! _4 r- q+ ^            var jStack = new Stack<int>();
5 H1 n4 Y2 j+ r3 W5 o            var i = NextLeaf(preOrderTraversal1, 0, iStack);
# |0 \1 @& Z& ^) ^* B# Q            var j = NextLeaf(preOrderTraversal2, 0, jStack);

# J, E* k3 L  \% _: Q  c            Console.WriteLine("Leaves: i {0}, j {1}", i, j);
( l' s1 i6 ^3 }  U7 ~$ r            while (i.HasValue && j.HasValue && preOrderTraversal1[i.Value] == preOrderTraversal2[j.Value])
$ @- _+ S. U; u            {
                i = NextLeaf(preOrderTraversal1, i.Value + 1, iStack);
  ]4 V' i1 @8 d) Y                j = NextLeaf(preOrderTraversal2, j.Value + 1, jStack);
! {5 }- f* n: w  ^9 S- ^            }

            Console.WriteLine("First mismatching leaves {0}, {1}", i, j);
7 c% u; D9 [  i! R2 i        }

This can't be done for a generic tree, since there's no way to determine the leaves based on a pre-order traversal array.