interview.md

Breadth first search

Uses a queue (FIFO)

var queue = new Queue<BinaryNode>();
queue.Enqueue(rootNode);
BinaryNode currentNode;

while (queue.Count != 0)
{
  currentNode = queue.Dequeue();
  if(currentNode.data == searchedData)
  {
    return true;
  }

  if(currentNode.Left != null)
    queue.Enqueue(currentNode.Left);

  if(currentNode.Right != null)
    queue.Enqueue(currentNode.Right);

    return false;
}

Depth first search

Uses a stack (LIFO)

var searchStack = new Stack<BinaryTreeNode>();
BinaryTreeNode _current;
_searchStack.Push(_root);

while (_searchStack.Count != 0)
{
    _current = _searchStack.Pop();
    if (_current.Data == data)
    {
        return true;
    }

    if(currentNode.Right != null)
        _searchStack.Push(_current.Right);

    if(currentNode.Left != null)
        _searchStack.Push(_current.Left);

    return false;
}

Data structure operations

-	Access	Search	Insertion	Deletion
Array	O(1)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)
Singly-Linked List	O(n)	O(n)	O(1)	O(1)
Hash Table	-	O(1)	O(1)	O(1)
Doubly-Linked List	O(n)	O(n)	O(1)	O(1)
Binary Search Tree	O(log(n))	O(log(n))	O(log(n))	O(log(n))