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;
}

All 10 Replies

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? :)

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;
}
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.

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

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
*/

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?

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.

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
s.push(node.left)
count++
if count>depth
depth = count
else if node.right exists and not in visited
s.push(node.right)
count++
if count>depth
depth = count
else
s.pop()
count--

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.

Good luck for your interview :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.