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).1 c8 M+ B% u$ N; s) d% n
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)) t0 Z7 J- [) A$ a$ g- w
# B9 S" O( c2 m) E5 A
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( ] {8 ?; i' I' @& X! _4 \. e
if (offset == preOrderTraversal.Length - 1)
9 x b! H$ R; `; x( m' p {+ u+ W! I0 S9 Q, `& `
return offset;$ d$ ^" A. q) K* M
}
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 {+ W0 ~ M" |) f; `. z R& c
return null;
' @* \8 B$ @( Y }% A: V7 o& h5 j, z0 g% z! w
# ?) R2 S( c2 I+ o* y* C
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 {) `5 P' } f: W5 E
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. ' j1 B& Q8 h3 I6 a6 ^( x) t
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 @, m2 H4 U6 Q; C4 ^' t( T( A
if (preOrderTraversal1.Length == 0 || preOrderTraversal2.Length == 0)
- r3 N2 p( G- t* Q& X+ Y {. [5 H: Y% r# F3 ?7 {; r! g
return;
2 n) A' G. M" L }& T+ T! F! u {# ]/ i3 o7 m& c
( t. i% H0 b& |7 z+ z0 Y3 V
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);3 [8 p! i6 O: U
# 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 {0 U3 C, W% p) \9 s' X) P. |6 R
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- ^ }) j0 @4 g3 ]; M/ \+ g. p0 |" M1 ?
; v3 A p! V. T+ b% t
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. |