3. Level and In #
Created Monday 03 February 2020
- Space segregator: InOrder as usual. Subtrees divided by the root.
- Root finder: Level order. First is the root.
Sufficiency and necessity is proven similar to Lecture 6 and 7.
Procedure:
- root = in.front()
- in_left_subtree = in[0:rootIndex]
- in_right_subtree = in[rootIndex+1:]
- level_left = level - all occurrences of the right subtree elements - o(nlogn), sorting, 2 pointer
- level_right = level - all occurences of the left subtree elements - o(nogn), sorting, 2 pointer
- root->left = f(level_left, in_left_subtree, int l1, int l2)
- root->right = f(level_right, in_right_subtree, int l1, int l2)
- Stop if root==NULL