CODEWITHSUNDEEP
javabinary-treebinary-search-tree
veinhorn
veinhorn

Reputation: 2403

Recursive binary tree insert

When I added node into binary tree and trying to show information about it, info isn't showing. I think that i have some problems with references in recursive insert algorithm, but can't fix it.

package test;

class BinaryTree<T> {
    private static class Node<T> {
        int key;
        T data;
        Node<T> leftChild;
        Node<T> rightChild;

        public Node(int key,T data) {
            this.key = key;
            this.data = data;
        }
    }

    public Node<T> rootNode;

    public BinaryTree() {
        rootNode = null;
    }

    public Node<T> getRootNode() {
        return rootNode;
    }

    // insert node into binary tree
    public void insertNode(int key,T data, Node<T> rootNode) {
        // to create new node

        // if tree doesn't have root elements
        if(rootNode == null) {
            rootNode = new Node<T>(key,data);
            rootNode.leftChild = null;
            rootNode.rightChild = null;
        }
        else {
            Node<T> focusNode = rootNode;

            if(key >= focusNode.key) {
                insertNode(key,data,focusNode.rightChild);
            }
            else {
                insertNode(key,data,focusNode.leftChild);
            }
        }
    }

    // inorder traverse tree
    public void inOrderTraverseTree(Node<T> focusNode) {
        if(focusNode != null) {
            inOrderTraverseTree(focusNode.leftChild);
            System.out.println(focusNode.data);
            inOrderTraverseTree(focusNode.rightChild);
        }
    }
}

public class MyApp {
    public static void main(String[] args) {
        BinaryTree<String> bintree = new BinaryTree<String>();
        bintree.insertNode(3, "Boss", bintree.rootNode);
        bintree.inOrderTraverseTree(bintree.rootNode);
    }
}

If I'm adding node with this algorithm and trying to show info, it works. How can i fix problem with recursive algorithm?

public void addNode(int key, T name) {
        Node<T> newNode = new Node<T>(key,name);
        if(rootNode == null) {
            rootNode = newNode;
        }
        else {
            Node<T> focusNode = rootNode;
            Node<T> parent;
            while(true) {
                parent = focusNode;
                if(key < focusNode.key) {
                    focusNode = focusNode.leftChild;
                    if(focusNode == null) {
                        parent.leftChild = newNode;
                        return;
                    }
                }
                else {
                    focusNode = focusNode.rightChild;
                    if(focusNode == null) {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

Thanks for any help.

Upvotes: 4

Views: 7780

Answers (1)

gerrytan
gerrytan

Reputation: 41143

Quick glance on your code -- I spotted on this part where you're checking for null, rootNode variable is local to the function. Hence the new Node you created gets thrown away immediately after the function quits, it won't change your member field

    // if tree doesn't have root elements
    if(rootNode == null) {
        rootNode = new Node<T>(key,data);
        rootNode.leftChild = null;
        rootNode.rightChild = null;
    }

You need to use this.rootNode = new Node<T>(key,data); instead, or use a different local variable name to avoid confusion

Upvotes: 3

Related Questions