Recording 23: Binary Search Trees

What defines a Binary Tree?

A data structure where each node at most 2 children called left & right child and there’s no order among the node values

What defines a Binary Search Tree?

A special kind of binary tree

• left subtree node is < root or nodes values

• right subtree node is > root or nodes values

Given this list of items (6,10,13, 9, 15,18,12) , draw it’s respective Binary Search Tree?

What’s the time complexity for a balanced BST?

O(log₂n) —> it’s spread out evenly making it faster as it doesn’t have to go through each branch

What is the time complexity of a unbalanced BST?

O(n) —> you would have to check every single branch in a tree which takes awhile

When provided starter code for a BST, be able to write an additional method of the same difficulty as count() or search().

• //total number of nodes

private int count(TreeNode<E> currentRoot) {

if (currentRoot == null) {

            return 0;

        }

        return 1 + count(currentRoot.getLeft()) + count(currentRoot.getRight());

    }

public int count() {

return count(root);

}

//return true if item is present

private boolean search(TreeNode<E> currentRoot, E findMe) {

if (currentRoot == null) {

            return false;

        }

        int cmp = findMe.compareTo(currentRoot.getData());

        if (cmp == 0) {

            return true;

        } else if (cmp < 0) {

            return search(currentRoot.getLeft(), findMe);

        } else {

            return search(currentRoot.getRight(), findMe);

        }

}

public boolean search(E findMe) {

return search(root, findMe);

}