CODEWITHSUNDEEP
javatreecomplexity-theory
Program125
Program125

Reputation: 65

Complexity of tree operations

I have this piece of code:

package rr.fe.op.lab.proc;

class TreeNode {
    TreeNode left;
    TreeNode right;
    String data;
}

class TreeProgram {
    public static void main(String[] args) {
        TreeNode node = null;
        node = insert(node, "Han");
        node = insert(node, "Luke");
        node = insert(node, "Leia");
        node = insert(node, "Padme");
        node = insert(node, "Vader");
        node = insert(node, "Yoda");

        System.out.println("Writing tree inorder:");
        writeTree(node);

        node = reverseTreeOrder(node);
        System.out.println("Writing reversed tree inorder:");

        writeTree(node);
        int size = sizeOfTree(node);
        System.out.println("Number of nodes in tree is "+size+".");

        boolean found = containsData(node, "Padme");
        System.out.println("Searched element is found: "+found);
    }

    static boolean containsData(TreeNode treeRoot, String data) {
        if(treeRoot == null)
            return false;
        else if(data.compareTo(treeRoot.data) == 0)
        return true;
        else if(data.compareTo(treeRoot.data) < 1)
            return containsData(treeRoot.left,data);
        else 
            return containsData(treeRoot.right,data);
    }

    static int sizeOfTree(TreeNode treeRoot) {
        if(treeRoot == null)
            return 0;
        else 
            return 1 + sizeOfTree(treeRoot.right) + sizeOfTree(treeRoot.left);
    }

    static TreeNode insert(TreeNode treeRoot, String data) {
        if(treeRoot == null){
            TreeNode newnode = new TreeNode();
            newnode.data = data;
            newnode.left = null;
            newnode.right = null;
            return newnode;
        }
        else if (data.compareTo(treeRoot.data) < 1)
            treeRoot.left = insert(treeRoot.left,data);
        else 
            treeRoot.right = insert(treeRoot.right,data);
        return treeRoot;
    }

    static void writeTree(TreeNode treeRoot) {
        if(treeRoot != null){
            writeTree(treeRoot.left);
            System.out.println(treeRoot.data);
            writeTree(treeRoot.right);
        }
    }

    static TreeNode reverseTreeOrder(TreeNode treeRoot) {
        if(treeRoot == null)
            return null;

        TreeNode node = new TreeNode();
        node = treeRoot.left;
        treeRoot.left = treeRoot.right;
        treeRoot.right = node;

        reverseTreeOrder(treeRoot.left);
        reverseTreeOrder(treeRoot.right);
        return treeRoot;
    }
}

I would like to know which is complexity (in big O notation) of method containsData. I know that method containsData will not found data after method reverseTreeOrder every time. But, I would like to write method contansData2 which will 100% find data in tree whereas it is reversed or not. In which complexity will that method be? Can you help me, please?

Upvotes: 0

Views: 217

Answers (1)

Jiri Tousek
Jiri Tousek

Reputation: 12440

The complexity will be O(n), because I can always give you input that will result in every new element being place to the right (or to the left) of each previous node, producing an unbalanced tree:

Input: a, b, c, d

Tree:

a
 \
  b
   \
    c
     \
      d

For most inputs, the tree will be more balanced and containsData() will be faster, but O notation cares about worst-case.

To make this O(log n) in terms of amortized complexity, you would have to rebalance the tree.

As for reversing the tree, this breaks the tree's invariant so that the containsData() method uses wrong tree branch when looking for the data. One solution would be to always search the whole tree, but that would nullify any benefit from the tree being sorted. Another approach could be using a "hack" - look at the root, compare the root data and left and right children's data to determine whether the tree was actually reversed then use this info to descend through the tree.

The worst-case complexity of this remains at O(n).

Upvotes: 1

Related Questions