Correctness und Performance in Binary Tree Search

[Amaris]

Can someone help me? I can't find the mistake.

The assignment Im working on:

Binary search tree (BST) is a binary tree where the value of each node is larger or equal to the values in all the nodes in that node's left subtree and is smaller than the values in all the nodes in that node's right subtree.

Write a function that checks if a given binary search tree contains a given value.

For example, for the following tree:

n1 (Value: 1, Left: null, Right: null)
n2 (Value: 2, Left: n1, Right: n3)
n3 (Value: 3, Left: null, Right: null)
Call to contains(n2, 3) should return true since a tree with root at n2 contains number 3.

Here my solution:

#include <stdexcept>
#include <string>
#include <iostream>

class Node
{
public:
Node(int value, Node* left, Node* right)
{
this->value = value;
this->left = left;
this->right = right;
}

int getValue() const
{
return value;
}

Node* getLeft() const
{
return left;
}

Node* getRight() const
{
return right;
}

private:
int value;
Node* left;
Node* right;
};

class BinarySearchTree
{
public:
static bool contains(const Node& root, int value)
{
Node* newRoot;
if (value > root.getValue())
{
newRoot = root.getRight();
}
else
{
newRoot = root.getLeft();
}

if( newRoot && newRoot->getValue() == value)
{
return true;
}
else if ( newRoot )
{
//recursive call
return contains (*newRoot, value);
}
return false;
}
};

#ifndef RunTests
int main()
{
Node n1(-4, NULL, NULL);
Node n3(3, NULL, NULL);
Node n2(0, &n1, &n3);

Node n5(5, NULL, NULL);
Node n7(7, NULL, NULL);
Node n6(5, &n5, &n7);

Node n4(3, &n2, &n6);

std::cout << BinarySearchTree::contains(n4, 0);
}
#endif

Compiles and works for the test example.
However, the test fails in Correctness
(for further automatically generated test cases I know not of)
and Performance (for very large trees).

Since I had this issue once before I would really appreciate a thorough explanation to finally fully understand the missing link in my thought pattern.

[Repeater]

Looks like your code never checks the value of the very first node.

[Amaris]

That is correct! Thanks, that solves the correctness issue.

Leaves the performance issue for large trees. Im not exactly sure when this performance issue occurs.

Could it mean when not in O(log n) but in O(n^2)?

From my opinion the algorithm is in O(log n) because it always searches in one side of the tree thus theoretically reducing the remaining nodes to one half on each iteration.

Is this not correct?

[jonnin]

are you asking theory stuffs?
in theory a binary search tree is binary, and find the item in log(n) rounded up (or +1 if you like).
but not all trees are binary. If you don't rebalance them, consider the less left, greater right algorithm. Now insert in order: 1,2,3,4,5,... 10
your tree is now a linked list and performs in O(N), as every value followed the greater right rule.
you have to rebalance it, find the central node (5 here) and rebuild off that.

in practice, it depends on what you want. A big tree that changes little, but is searched a lot, is better stuffed into a vector (even if you take the [index] of the vectors and use those as 'pointers' to make a 'tree' out of it). A big tree that changes a lot needs some thought and design to make it perform at the max, as page faults and memory problems plague standard pointer trees but vectors are frustrating with inserts/updates. You have to think through what the data structure will DO most of its life and make THOSE operations as efficient as can be. The classic structures are a starting point, but often you need a hybrid if you want speed.

Your understanding is correct. It throws away 1/2 each time if balanced. The more out of balance it gets, the less it is like lg(n) and it slowly becomes O(n).