using a stack to get the height of a BST

[aaronmk2]

I am trying to get the height of a BST using a stack. I was told that I should use preorder and measure find the largest size of the stack. However, this does not seem to work. Any ideas of what I am doing wrong.

int PBT::maxDepth() {
	if (!root) {
		return -1;
	}
	int depth=0;
	stack<TreeNode *>s;
	TreeNode * nodePtr=root;
	for (; ; ) {		
		while (nodePtr) {
			s.push(nodePtr);
			if (s.size() > depth)
				depth = s.size();
			nodePtr=nodePtr->left;
		}if (s.empty()) {
			break;
		}
		nodePtr=s.top();
		s.pop();
		nodePtr=nodePtr->right;
	}
	return depth;
}

[Taywin]

I'm trying to follow your code here...

for (; ; ) {
  while (nodePtr) {  // count the depth of 'left-hand' nodes
    s.push(nodePtr);
    if (s.size() > depth)
      depth = s.size();
    nodePtr=nodePtr->left;
  }

  // problem here, if the tree has only "right hand" node, it will prematurely break
  if (s.empty()) {
    break;
  }

  nodePtr=s.top();  // the node becomes the "last" left hand node
  s.pop();
  nodePtr=nodePtr->right;  // try to go to the right hand node of the "last" left hand node
}

Hope you see the problem here. I think you may need to rethink for algorithm in a paper first? :)

[aaronmk2]

I tried this way and it still does not work.

int PBT::maxDepth() {
	if (!root) {
		return -1;
	}
	int depth=0;
	int count=0;
	stack<TreeNode* >s;
	TreeNode * nodePtr=root;
	depth++;
	s.push(nodePtr);
	while (!s.empty()) {
		nodePtr=s.top();
		s.pop();
		depth--;
		if (nodePtr->right) {
			s.push(nodePtr->right);
			depth++;
		}
		if (nodePtr->left) {
			s.push(nodePtr->left);
			depth++
		}
		if (depth>count) {
			count=depth;
		}
		
	}

	return count;
}

[Taywin]

int depth=0;
int count=0;
stack<TreeNode* >s;
TreeNode * nodePtr=root;
depth++;
s.push(nodePtr);
while (!s.empty()) {
  nodePtr=s.top();
  s.pop();
  depth--;  // why decrement depth???

  // check if there exists right hand node?
  if (nodePtr->right) {
    s.push(nodePtr->right);
    depth++;
  }

  // check if there exists left hand node?
  if (nodePtr->left) {
    s.push(nodePtr->left);
    depth++
  }

  // not sure what this one for???
  if (depth>count) {
    count=depth;
  }
		
}

return count;

You are almost there :) You may actually use BFS (Breadth First Search) to count the height while using stack as the storage counter. Whenever you go to the next tree height, increment the depth.

[aaronmk2]

You lost me, how would I used a BFS to count the height? I tried with a BFS and had the same problem.

[Taywin]

I'm sorry, I forgot that you are using stack. BFS is for queue, but DFS is for stack. How you do it? It is simple. When you push, increment the counter, and when you pop decrement the counter. Each time you push, you check if the value incremented is greater than your current holding depth. If it does, the depth is equal to the counter; otherwise, ignore. Once you are done, your counter should be equal to 0 while your depth is the maximum height of the tree.

The only thing left is to implement. It is really straight forward, but you need to think a bit about how to implement it. If you still do not get the idea, please let me know.

/*
For example:
         20
       /    \
      /      \
     15      17
   /   \    /   \
  4    9   5    11
      /           \
     2             7
                    \
                     3

Let say the tree above is one of your tree.
DFS will search for left hand first, then right
  Init:
    s is an empty stack
    s.push(20)
    depth = 1
    count = 1
  Start:
    s.push(15)       // left hand of the node 20 is 15
    count <- 2       // increment
    depth <- count   // depth < counter , so depth = counter or 2
    s.push(4)        // left hand of the node 15 is 4
    count <- 3       // increment
    depth <- count   // depth = 3
    // no children here, go back...
    s.pop()          // pop 4
    count <- 2       // decrement
    s.push(9)        // right hand of node 15 is 9
    count <- 3       // increment
    // no left hand child
    s.push(2)        // right hand of node 9 is 2
    count <- 4       // increment
    depth <- count   // depth = 4
    // no children here, go back...
    s.pop()          // pop 2
    count <- 3       // decrement
    // no more children to check, go back...
    s.pop()          // pop 9
    count <- 2
    s.pop()          // pop 15
    count <- 1
    s.push(17)
    count <- 2
    s.push(5)
    count <- 3
    // no children here, go back...
    s.pop()          // pop 5
    count <- 2
    s.push(11)
    count <- 3
    s.push(7)
    count <- 4
    s.push(3)
    count <- 5
    depth <- count   // depth = 5
    // no children here, go back...
    s.pop()          // pop 3
    count <- 4
    s.pop()          // pop 7
    count <- 3
    s.pop()          // pop 11
    count <- 2
    s.pop()          // pop 17
    count <- 1
    s.pop()          // pop 20
    count <- 0
  done...

  return depth
*/

[aaronmk2]

I have been playing around with the logic for hours and still have had no luck. The problem I am having is that after I pop 4 I pop 15 before pushing 9. According to what you showed me I should only pop 15 after I popped all the child nodes for 15. This is where my problem is, any tips or clues?

[Taywin]

OK... The loop could be somewhat like this...

while !s.empty()
  node = s.top()
  if node.left exits
    s.push(node.left)
    count++
    if count>depth
      depth = count
  else if node.right exists
    s.push(node.right)
    count++
    if count>depth
      depth = count
  else
    s.pop()
    count--

That's just a simple idea. Remember, this example may create an infinite loop because I didn't take time to think about it thoroughly. You need to create a way to deal with that in your implementation and adjust it to your data structure. Using recursive would be easier in my opinion.

[Taywin]

OK I just tried to implement it, the loop creates an infinite loop because it doesn't know whether or not a node is visited. To solve the issue, you need to add a variable that keep track of visited nodes. That's all.

visited <- empty array
while !s.empty()
  node = s.top()
  if node.left exits and not in visited
    add node.left to visited
    s.push(node.left)
    count++
    if count>depth
      depth = count
  else if node.right exists and not in visited
    add node.right to visited
    s.push(node.right)
    count++
    if count>depth
      depth = count
  else
    s.pop()
    count--

[aaronmk2]

Thanks for all your help. If was easy to get in running recursively but I am preparing for an interview and was told to practice converting a BST for resurrection to using stacks and queues.

[Taywin]

Good luck for your interview :)