Mastodon

Binary Trees

I've moved on to trees, and I have many trees to cover.

The types of trees I'm studying:

  • binary search tree: BST
  • red/black tree
  • splay trees
  • AVL trees
  • B-Trees:
  • 2-3 (type of B-tree) Search Trees
  • N-ary trees
  • Tries
  • Heap
  • Binary Heap
  • Disjoint Sets
  • Priority Queue

Here are a few code samples for searching a binary search tree for an integer value, getting the height of the tree (in nodes, not edges), and a postorder deletion to free memory.

bool Search(BSTNode* node, int value) {  
  if (node == nullptr) {
    return false;
  }

  if (value < node->data) {
    return Search(node->left, value);
  } else if (value > node->data) {
    return Search(node->right, value);
  } else {
    return true;
  }
}

int GetHeight(BSTNode* node) {  
  if (node == nullptr) {
    return 0;
  }

  return 1 + std::max(GetHeight(node->left), GetHeight(node->right));
}

void DeleteTree(BSTNode* node) {

  if (node == nullptr) {
    return;
  }

  DeleteTree(node->left);
  DeleteTree(node->right);

  delete node;
}

Want to see more? Read all my BST code here.

comments powered by Disqus