The idea behind 10.12.2

#1

Hi, I’m trying to solve the problem constructing a max-tree by array of distinct integers.

The idea is that we find max element from array (say with index m) and set it as root and left and right it’s descendents are max elements from (0, m-1) and (m+1, n) respectively. The algorithm complexity should be O(n).

I understand that array is an inorder traversal of the tree, but cannot realize what to do further.

0 Likes

#2

I think I have managed to solve it. Comments welcome.

Firstly, let us consider the stack-less and recursion-less traversal of binary trees, where each node has a parent pointer.
This can be done by getting the leftmost node and successively getting the inorder successor. If a node has a right child, the inorder successor is the leftmost node in the right subtree. Otherwise, it is the first ancestor whose left child is an ancestor of given node.
For some nodes, getting the inorder successor may take O(height) time, but amortized over the whole tree, it takes O(n) time. Apologies for not proving this here; CLRS has a comprehensive proof. This fact will be used later on.

Secondly, observe the structure of the max-tree that will be created. It looks like a max heap. Hence, all root to node paths are strictly decreasing and similarly, all node to ancestor/root path is strictly increasing. This is an important point.

My algorithm scans the array from left to right, maintaining:

  1. A binary tree.
  2. A pointer to the last inserted node. This is like the hint in C++ STL map.
    Done properly, it is exactly equivalent to the inorder traversal described above and thus, will take O(n) time.
    Here is how insertions work:
    Compare the array element being scanned to the just inserted binary tree node. If the array element is less than the current node, clearly it is a child. Otherwise, it is an ancestor.

If the new node is a child, I recursively construct the right subtree keeping in mind to not exceed the array boundary and also, not to exceed the value of the current pointer (no child can exceed the value of an ancestor).

If the new node is a parent, we simply have to go to the root of the current tree being constructed (local to the function) and attach it as a left child of a new node.

Here (Github gist) is the solution and testing code in C++. The testing code works by comparing the trees created by my algo and the obvious O(n log n) solution.

Edit: Forget the inorder traversal complexity proof. I am never traversing the height of the tree in my solution and scanning each element only once. Time complexity is O(n).

Comments/Suggestions are welcome.

1 Like

#3

I think your method is correct (The problem number should be 10.10.2). I could not find any solution until reading your post.

The following is my implementation using stack, without recursion. I just tested it manually.

unique_ptr<BTNode<int>> ConstructMaxTree(const vector<int>& inputs) {
	if (inputs.empty()) return nullptr;

	stack<BTNode*> parents;
	unique_ptr<BTNode<int>> root(new BTNode<int>{inputs[0]});
	parents.emplace(root.get());
	int cur = 1;
	while (cur < inputs.size()) {
		int cur_value = inputs[cur];
		if (cur_value < parents.top()->data) {
parents.top()->right = unique_ptr<BTNode<int>>(new BTNode<int>{cur_value});
             	 	parents.emplace(parents.top()->right.get());
		} else {
			parents.pop();
			while (!parents.empty() && parents.top()->data < cur_value)
				parents.pop();

			unique_ptr<BTNode<int>> new_node(new BTNode<int>{cur_value});
			if (!parents.empty()) {
			new_node->left = move(parents.top()->right);
			parents.top()->right = move(new_node);
			parents.emplace(parents.top()->right.get());
		} else {
                       new_node->left = move(root);
                       root = move(new_node);
                       parents.emplace(root.get());
		}
		}	
		++cur;
	}
	return root;
}
/* Test 7 8 9 4 1 3 5 */
0 Likes

#4

Thank you for the explanation.
I think for some trees this: “we simply have to go to the root of the current tree being constructed” may take more than O(n) to construct. What if the parent of the element to be inserted is somewhere in the middle of the tree?

I mean what if you want to add 8 to the trees below (add something in between over and over again)?
First example:
tree1
Second example:
tree2

0 Likes

#5

With the solution I posted, we are never going to insert somewhere in the middle of the tree. The way the construction will work is we will have a hanging forest of trees, mid-way in construction, that will all join in the end.

Why don’t you try pretty printing the binary tree at each step with ducalpha@'s test example and my code:

Also:

I was referring to an individual tree in this forest of trees that I described. The operation I described is an O(1) time operation. Have a look at this.

1 Like