Traversing through a Array-Binary tree

Question

I have troubles with traversing through a array binary tree without recursion. I hope someone can tell me what iam doing wrong. For simplicity the code is kept simple.

Please note: Its not allowed to add other methods like Iterator to check if there is a hasNext() and so on.

For now i just want to print all keys out (incl. child keys) in the hope that i can do the rest of the learning!

Thank you very much for helping.

public class BTree {

    private Node root;

    public BTree(Node root) {
        this.root = root;
    }

    public int getMaxKey() {
        Node copy = root;

        for (int i = 0; copy.child != null && i < copy.child.length; i++) {
            System.out.println("key: " + copy.key); // output: 15, 80
            if (copy.child != null) {
                copy = copy.child[i];
            }

        }

        return 0;
    }
}

public class Node {
    public int key;
    public Node[] child;

    public Node(int key, Node[] child) {
        this.key = key;
        this.child = child;
    }
}

public class NodeMain {

    public static void main(String[] args) {
        Node[] lv1Nodes = new Node[2];
        lv1Nodes[0] = new Node(25, null);
        lv1Nodes[1] = new Node(99, null);

        Node[] lv0Nodes = new Node[2];
        lv0Nodes[0] = new Node(80, lv1Nodes);
        lv0Nodes[1] = new Node(5, null);

        Node root = new Node(15, lv0Nodes);

        BTree bTree = new BTree(root);
        int maxKey = bTree.getMaxKey(); // output should be 99
        System.out.println(maxKey);
    }

}

Abinash · Accepted Answer · 2021-07-30 02:27:52Z

1

So, here you are following only one branch till null for the Binary tree traversal. But, you need to keep track of all nodes in traversal order of child array so that you can get the max element from it.

please refer to below code, here i've used stack to keep all of the value array nodes, which we can pop and check for maxValue.

public class BTree {
    private final Node root;

    public BTree(Node root) {
        this.root = root;
    }

    public int getMaxKey() {
        int maxKey = root.key;
        Stack<Node> stack = new Stack<>();
        stack.addAll(Arrays.asList(root.child));
        while(!stack.isEmpty()){
            Node node = stack.pop();
            System.out.println(node.key);
            if(node.key > maxKey)
                maxKey = node.key;
            if(node.child != null)
                stack.addAll(Arrays.asList(node.child));
        }
        return maxKey;
    }
}

Edit: I've created a image which can help us to understand the tree little bit more clearly, and i've used for my reference for this code.

edited Jul 30, 2021 at 2:27

answered Jul 30, 2021 at 1:53

Abinash

3012 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Jotaro Over a year ago

thank you for your answer. I totally forgot that you always follow one path if you choose iterative operation. That was the missing link for me! If you choose recursive operation you follow multiple paths. I actually do not have any problem with your solution, but i tried one without a Stack. Feel free to have a look at it.

Abinash Over a year ago

Hi @Jotaro your solution holds true, for node child value which has less than or equal two nodes. What if the node child values goes beyond two?

Jotaro Over a year ago

i was thinking about this before. i would say that you can not have more than two nodes because binary trees does not support it. a binary tree is a tree data structure in which each node has at most two children en.wikipedia.org/wiki/Binary_tree btw: i like your solution more (because its much shorter and cleaner), but i was searching for a solution without any other data structure.

Abinash Over a year ago

Oh, yeah i forgot about that part. Sorry about that. Your solution is more space optimal in that case. Thank you.

Jotaro · Accepted Answer · 2021-07-31 11:07:34Z

My solution without Stack object:

public int getMaxKey() {
        Node copy = root;
        int max = -1;

        while (copy.child != null) {
            if (max < copy.key)
                max = copy.key; //root

            if (copy.child.length == 1) { // max key between parent and child node, only one path available
                if (max < copy.child[0].key) {
                    max = copy.child[0].key;
                    copy = copy.child[0];
                }

            } else if (copy.child.length == 2) { // max between two nodes, decide between one path
                int maxBetweenChild = Math.max(copy.child[0].key, copy.child[1].key);
                Node node = Arrays.stream(copy.child).filter(n -> n.key == maxBetweenChild).findFirst().get();
                copy = node;

                if (max < maxBetweenChild)
                    max = maxBetweenChild;
            }
        }

        return max;
    }

Collectives™ on Stack Overflow

Traversing through a Array-Binary tree

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related