Question

oOk guys i want to add a method to the LinkedBinaryTree class that returns the height of a tree and another method in BTNode that does most of the work. First, check to see if the root is null. If it is, then the tree is obviously empty and return 0. If it is not null, return root.height().

import java.util.Iterator;


public class LinkedBinaryTree implements BinaryTree { protected BTNode root; //----------------------------------------------------------------- // Creates an empty binary tree. //----------------------------------------------------------------- public LinkedBinaryTree() { root = null; } //----------------------------------------------------------------- // Creates a binary tree with the specified element as its root. //----------------------------------------------------------------- public LinkedBinaryTree (T element) { root = new BTNode(element); } //----------------------------------------------------------------- // Creates a binary tree with the two specified subtrees. //----------------------------------------------------------------- public LinkedBinaryTree (T element, LinkedBinaryTree left, LinkedBinaryTree right) { root = new BTNode(element); root.setLeft(left.root); root.setRight(right.root); } //----------------------------------------------------------------- // Returns the element stored in the root of the tree. Throws an // EmptyCollectionException if the tree is empty. //----------------------------------------------------------------- public T getRootElement() { if (root == null) throw new EmptyCollectionException ("Get root operation " + "failed. The tree is empty."); return root.getElement(); } //----------------------------------------------------------------- // Returns the left subtree of the root of this tree. //----------------------------------------------------------------- public LinkedBinaryTree getLeft() { if (root == null) throw new EmptyCollectionException ("Get left operation " + "failed. The tree is empty."); LinkedBinaryTree result = new LinkedBinaryTree(); result.root = root.getLeft(); return result; } //----------------------------------------------------------------- // Returns the element in this binary tree that matches the // specified target. Throws a ElementNotFoundException if the // target is not found. //----------------------------------------------------------------- public T find (T target) { BTNode node = null; if (root != null) node = root.find(target); if (node == null) throw new ElementNotFoundException("Find operation failed. " + "No such element in tree."); return node.getElement(); } //----------------------------------------------------------------- // Returns the number of elements in this binary tree. //----------------------------------------------------------------- public int size() { int result = 0; if (root != null) result = root.count(); return result; } public Iterator iterator() { return new ArrayIterator(); } }

Answer 1

@ganeshie8

Answer 2

@hartnn

Answer 3

Since the tree isn't balanced it will in worst case behave like a linked list. This means that you in worst case have to visit each node once.

A fairly simple way to do this is to have a recursive metod which returns the largest depth of it's children in the BTNode class.

Something like
```
method height(BTNode node)
if node equals null
return 0

int lHeight, rHeight

lHeight = height(node.left)
rHeight = height(node.right)

return largest(lHeight, rHeight) + 1
end
```

You call this metod from the method in the LinkedBinaryTree class and pass root as argument.

Notice how this method has bad memory complexity (O(N)) as each recursive call add some stuff to the stack, but in return the logic is compact and and easy compared to an iterative approach.

Answer 4

You might also/instead want to have another overloaded version of height in BTNode which initializes the first height method with the current node as parameter to achive root.height() specification. The catch is that like you wrote, you'll manualy have code the first check if root is null.

```
method height()
return hight(this)
end
```

Answer 5

Lyrae, the memory complexity is not excessive; it is only O(height of tree). For reasonably balanced trees consisting of N nodes, this is ~ O(logN). Moreover, there is no obvious way to improve upon this algorithm.

Also, note that you must always visit every node in the tree -- whether the tree is perfectly balanced or a chain.

If I were to remove the recursive overhead, I would directly use a stack, avoiding some overhead:

s.height() -> Integer
Record:
height: Integer
ref: Pointer[BinaryNode]

s: stack[Record]
s.push(Record(height = 0, ref = root))
maxi: Integer = 0

while not s.empty():
t <- s.pop()
if t.ref not null
s.push(Record(height = t.height + 1, ref = t.ref.left))
s.push(Record(height = t.height + 1, ref = t.ref.right))
else
maxi = max(maxi, t.height)

return maxi

This saves some space (only state stored is the height of each node, and a pointer) and time (less function call overhead). But, it's probably not that much better in either of these categories -- but it's a simple, isolated change that can be done without fear of breaking other things.

If using multiple processors, then you need some extra overhead for synchronization purposes. But, if implemented efficiently, you ought to see a near linear speed-up with the number of cores. That said, the average space complexity is worse (compared to the serial implementation), but the worst-space complexity remains the same.