CODEWITHSUNDEEP
javabinary-tree
lzc
lzc

Reputation: 1705

Size of a binary tree with non recursive method Java

Hello I'm trying to write a non recursive method for getting the size of a node since recursion in Java is expensive. This would include the number of child nodes + 1 (itself). I've converted an C implementation How can I get number of leaf nodes in binary tree non-recursively? in to Java but it's not correct.

Edit: algorithm for counting the size of binary tree, non recursively.

public int size(Node n) {
    Stack<Node> sizeStack = new Stack();
    int count = 1;//includes the n node
    if(n == null) {
        return 0;
    }
    sizeStack.push(n);
    while(!sizeStack.isEmpty()){
        node = sizeStack.pop();
        while(node != null) {
            count++;
            if(node.right != null){
                sizeStack.push(node.right);
            }
            node = node.left;
        }
    }
    return count;
}

Upvotes: 0

Views: 3356

Answers (2)

KeyC0de
KeyC0de

Reputation: 5257

Here is a C implementation. RealSkeptic's method above was not that intuitive to me. I provide comments and it should be pretty easy to follow.

int sizeOfBsTree_nonRec(TreeNode *root)
{
    if (root == NULL) {
        return 0;
    }

    int size = 0;
    Stack S;
    initializeStack(&S);

    // Push to the stack all Nodes in the (sub)tree and
    // increase the counter when you pop one out
    push(root, &S);
    while(!isStackEmpty(&S)){
        root = pop(&S);
        size++;

        if (root->right != NULL)
            push(root->right, &S);
        if (root->left != NULL)
            push(root->left, &S);
    }

    return size;
}

Upvotes: 1

RealSkeptic
RealSkeptic

Reputation: 34628

Your algorithm is counting leaf nodes. Your own wish was to count all the nodes. An algorithm for counting leaf nodes only adds to the counter when it pops a leaf node, and that's true both for Java and for C. So actually your program is good - but not for the problem you have defined.

In order to count all the nodes, you have to increment the counter every time you pop a node from the stack. This means you have to push all the nodes, rather than loop the way you have for the leaf nodes.

If you want to save on push operations (which is the only reason why this algorithm will be better than recursion, unless the tree is unbalanced towards the right) you should just increment the counter for every node that you are examining, but keep the basic loop as it was. 

public int size(Node n) {
    Stack<Node> sizeStack = new Stack();
    int count = 1;//includes the n node
    if(n == null) {
        return 0;
    }
    sizeStack.push(n);
    while(!sizeStack.isEmpty()){
        node = sizeStack.pop();
        while(node != null) {
            count++;
            if(node.right != null){
                sizeStack.push(node.right);
            }
            node = node.left;
        }
    }
    return count;
}

Upvotes: 1

Related Questions