t-complexity: O(N) N is number of nodes
s-complexity: O(N) in worst case, recursion depth is N
three cases for root is p and q's lowest common ancester:
p and q are in root's sub-trees, and is not in same side
p == root, q is in root's left or right sub-tree
q == root, p is in root's left or right sub-tree
Last updated