find_root (A[], i): prev = i if (A[prev]->left != NULL || A[prev]->right != NULL): cur = prev #not a leaf else: cur = prev + 1 while (cur < MAX): if (A[cur]->left != NULL && A[cur]->left !=A[prev]): return cur if (A[cur]->right != NULL && A[cur]->right != A[cur+1]): tgt,next_cur = find_root (cur+1) if (A[cur]->right == A[tgt]): prev = cur cur = next_cur+1 elif (A[cur]->right != NULL): prev = cur cur += 2 else: prev = cur cur ++ return prev,cur #final return value of cur is root