CODEWITHSUNDEEP
javarecursiondata-structuresbinary-tree
Strategiger
Strategiger

Reputation: 55

Printing branches on a Binary Tree

How do you count number of branches, in this case branches with even integers. Here's what I have so far. It seems to work for a couple of the cases.

public int evenBranches() {
    return evenBranches(overallRoot);
}

private int evenBranches(IntTreeNode root) {
    if (root == null) {
        return 0;
    } 
    int val = 0;
    if (root.left != null) {
        val += evenBranches(root.left);
    } else if (root.right != null) {
        val += evenBranches(root.right);
    }
    if (root.data % 2 == 0) {
        return val + 1;
    } else {
        return val;
    } 
}

enter image description here

Upvotes: 2

Views: 488

Answers (3)

Tanmay Garg
Tanmay Garg

Reputation: 841

You can very well achieve the desired results by using a global variable, and applying BFS (breadth first search) on your tree, in this manner:

int evencount = 0; // global-var.
public int evenBranches() {
    evenBranches(overallRoot);
    return evencount;
}
private void evenBranches(IntTreeNode root) {
    if(!root) return;
    if( (root.left || root.right) && (root.data % 2 == 0)){
        evencount++;
    }
    evenBranches(root.left);
    evenBranches(root.right);
}

Upvotes: 0

pbajpai
pbajpai

Reputation: 1369

You can modify the evenBranches() method as below: I think It will cover all edge cases, If any testcase is left, let me know, I will fix it.

    public int evenBranches() {
        return evenBranches(overallRoot, 0);
    }

    private int evenBranches(IntTreeNode root, int count) {
        if(root == null || (root.left == null && root.right == null)) {
            return count;
        }
        if(root.data % 2 == 0) {
            count++;
        }
        count += evenBranches(root.left, count);
        count += evenBranches(root.right, count);
        return count;
    }

Upvotes: 1

Rajeev Sampath
Rajeev Sampath

Reputation: 2747

You may need to remove the else condition when checking the occurrences in right branch. Otherwise it will check only one side. eg:

private int evenBranches(IntTreeNode root) {
    if (root == null) {
        return 0;
    } 
    int val = 0;
    if (root.left != null) {
        val += evenBranches(root.left);
    } 

    if (root.right != null) {
        val += evenBranches(root.right);
    }
    if (root.data % 2 == 0) {
        return val + 1;
    } else {
        return val;
    } 
}

Upvotes: 0

Related Questions