Friday, September 13, 2013

optmized code for printing max path length in a BST

public void OptimizedMaxPath() {
        OptimizedMaxPath(root);
    }

    private void OptimizedMaxPath(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        int count = 0, fMax = 0, sMax = 0;
        Node fNode = root, sNode = null; Node delNode = null;
        while (true) {
            while (node != null) {
                stack.push(node);
                 count++;
                node = node.leftChild;
               }
            if (stack.size() == 0) break;
                node = stack.pop();
                  if (fMax < count) {
                        sMax = fMax;
                        fMax = count;
                        fNode = node;
                    }
                    if (fMax > count && count > sMax) {
                        sMax = count;
                        if(fNode.parent!=sNode)
                        sNode = node;
                    }
                count--;
                node=node.rightChild;
      }
        System.out.print("\n nodes height" + fNode.data + " : " + sNode.data + "\n");
        Stack<Node> rStack = new Stack<Node>();
        while(true){
            if(fNode==root)break;
            if(fNode.parent!=null && fNode.parent.data > sNode.data)break;
            System.out.print(fNode.data+" : ");
            fNode=fNode.parent;
        }
        while (sNode!=fNode) {
            System.out.print(rStack.push(sNode) + " : ");
            sNode=sNode.parent;
        }
        while(!rStack.isEmpty())
            System.out.print(rStack.pop().data+" : ");
    }

No comments:

Post a Comment