*Working on the implemenation of the Binary Search Tree. Re-implement the int de
ID: 3730823 • 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.
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
Please find my implementation using A Queue in O(N) time.
import java.util.LinkedList;
import java.util.Queue;
public class IterDepth {
// use NULL as a marker at every level, so whenever we encounter null, we
// will increment the height by 1
public int depth(TreeNode root) {
Queue<TreeNode> q = new LinkedList<TreeNode>();
int height = 0;
// add root to the queue
q.add(root);
// add null as marker
q.add(null);
while (q.isEmpty() == false) {
TreeNode n = q.remove();
// check if n is null, if yes, we have reached to the end of the
// current level, increment the height by 1, and add the another
// null as marker for next level
if (n == null) {
// before adding null, check if queue is empty, which means we
// have traveled all the levels
if(!q.isEmpty()){
q.add(null);
}
height++;
}else{
// else add the children of extracted TreeNode.
if (n.left != null) {
q.add(n.left);
}
if (n.right != null) {
q.add(n.right);
}
}
}
return height;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.left.left.right = new TreeNode(8);
IterDepth i = new IterDepth();
System.out.println("Tree Height " + i.depth(root));
}
}
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.