*Working on the implemenation of the Binary Search Tree. Re-implement the int de
ID: 3731152 • Letter: #
Question
*Working on the implemenation of the Binary Search Tree.
Re-implement the int depth() method to use a software stack, rather than recursion. Use stacks NOT queues!
The depth returns the depth of the longest branch in the tree
Hint: Use two stacks.
public int depth()
{
return depth(this.root);
}
private int depth(TreeNode current)
{
if(current == null)
{
return -1;
}
else
{
int leftDepth = depth(current.left);
int rightDepth = depth(current.right);
if(leftDepth > rightDepth)
{
return leftDepth + 1;
}
else
{
return rightDepth + 1;
}
}
}
Explanation / Answer
Following iterative function uses two stacks to find depth of binary tree (implemented using JAVA):
private int depth(TreeNode current)
{
int dep=-1; //base case
//create two stacks
//s_exp stores the nodes which needs to be explored
Stack<TreeNode> s_exp = new Stack<>();
//s_path stores the path from root to parent of current node
Stack<TreeNode> s_path = new Stack<>();
//push the root node to s_exp
s_exp.push(current);
while(!s_exp.empty())
{
current=s_exp.peek(); //read the node on top of stack
//if top of both stacks are same, it means we have explored every node below it and can pop it
if(!s_path.empty && current == s_path.peek())
{
//update depth if current path is longer
if(s_path.size() > dep)
dep=s_path.size() -1 ;
//popping nodes and heading towards its sibling or parent is similar to returning the function call in recursion
s_path.pop();
s_exp.pop();
}
else
{
s_path.push(current);
//push both its child ,right and then left so as to explore left child first. (You can do the other way as well)
if(current.right != null)
s_exp.push(current.right);
if(current.left != null)
s_exp.push(current.left);
//the very first time when top of both stacks become same, it is due to current node being reached to leaf
}
}
return dep;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.