What shall I do to create a binary tree by taking depth as input in java?

user_13986135 0
Viewed 94

In my case, I want to create a binary tree by taking the depth as the input.

For example, if I do tree.create(3), there will generate a binary tree when the depth of the deepest left is three, which means there will be 2^3 - 1 nodes in the tree and the value of all of them will be 0. The index will be 0 - 6 accorndingly.

class Tree<T> {

    int depth;
    int index;
    T value;

    public Tree(int index,T value) {
        this.index = index;
        this.value = value;
    }

    public static <K> Tree<K> create(int depth){
        if(depth >= 1) {

            //return a tree with the inputting depth, 
            //but I don't know how to do in this step

            return new Tree(...?)
        }
    } 
}

Which part of knowledge shall I use to achieve this in Java? Thanks!

data-structures java
1 Answers

Usually when working with a binary tree data structure you need to write recursive methods. When writing a recursive method, you need to write a condition that terminates the recursion. In your case, the recursion will end if we have reached the desired depth. In order to determine if we have reached the desired depth, we need to know what that desired depth is and what the current depth is. I will assume that the depth of the root node in the binary tree is zero. This means that for a maximum depth of 3 (as in the example in your question), the deepest level will be level 2. If we have not reached the desired depth, then I need to add a left and a right child node and then call the same method on each of those children and make sure that the depth of the child nodes is one greater than the depth of the parent. So my recursive method needs three parameters:

  • a node to (possibly) add child nodes to
  • the current depth
  • the maximum depth

Note that I don't need to handle the value (or data) that each node contains because you state, in your question, that each node will have the same value. Hence I can simply copy the value from the parent node to each of its children.

Here is a complete example. Note that when I tested it, a depth greater than 25 causes an OutOfMemoryError because there is a limit on how many recursive method invocations can be done.

import java.util.ArrayList;
import java.util.List;

public class BinTree<T> {
    BinTreeNode<T>  root;

    public static <T> BinTree<T> create(int depth, T val) {
        if (depth > 0) {
            BinTree<T> theTree = new BinTree<>();
            theTree.root = new BinTreeNode<>(val);
            theTree.addLevel(theTree.root, 0, depth);
            return theTree;
        }
        else {
            throw new IllegalArgumentException("Invalid depth: " + depth);
        }
    }

    public void getAllElements(BinTreeNode<T> aNode, List<T> list) {
        if (aNode == null) {
            return;
        }
        else {
            getAllElements(aNode.left, list);
            list.add(aNode.genericObject);
            getAllElements(aNode.right, list);
        }
    }

    private void addLevel(BinTreeNode<T> theNode, int level, int deepest) {
        if (level == deepest - 1) {
            return;
        }
        theNode.left = new BinTreeNode<>(theNode.genericObject);
        theNode.right = new BinTreeNode<>(theNode.genericObject);
        addLevel(theNode.left, level + 1, deepest);
        addLevel(theNode.right, level + 1, deepest);
    }

    public static void main(String[] args) {
        BinTree<String> aTree = BinTree.create(3, "George"); // max depth = 25
        List<String> list = new ArrayList<>();
        aTree.getAllElements(aTree.root, list);
        System.out.println(list.size());
    }
}

class BinTreeNode<T> {
    BinTreeNode<T> left, right;
    T genericObject;

    public BinTreeNode(T obj) {
        genericObject = obj;
    }
}

Note that I added method getAllElements as a test to see whether the correct number of nodes were created.

user_21643650
Related