Created: 2023-10-02 22:21
Status: #concept
Subject: Programming
Tags: C Data Structure Linked List Tree Heap

Binary Tree

It is a Node-based hierarchal data structure where a single node branches out to two other nodes, left and right.

  • they have no Graph cycles, similar to graph theory Trees.

Subtypes of Binary Trees

The height of a binary tree is defined as the number of Edges from the root node to the deepest leaf node.

  1. Full or Perfect Binary Tree
    • every node, except the Leaves, has exactly two children.
    • it has 2h+1−1 nodes, where h is the height (number of edges to the leaf) of the tree.
  2. Complete Binary Tree
    • every level of the tree is completely filled, except for the last level which can be partially filled.
    • new nodes are inserted starting from the leftmost side of the last level.
  3. Balanced Binary Tree
    • the height of the left & right subtrees of every node differ by at most 1.

Kinds of Traversals

These traversals allow us to list out or printf the elements of a tree.

  1. Depth-First Search (DFS)
  2. Breadth-First Search (BFS)

Array Implementation

An array can represent a tree, where the indices represent positon of the nodes of a tree and the elements are the values inside each node.

Let parent, leftChild, rightChild, child be valid indices of an array a.
We can derive the formula to get the nodes like so:

  • leftChild = (2*parent) + 1
  • rightChild = (2*parent) + 2
  • parent = (child-1) / 2
#define MAX 10

typedef struct heap {
  int arr[MAX];
  int lastIndex;
} HeapType;
Since we always insert elements into the next available leaf node, this is a Complete Binary Tree.

Binary Search Trees

The node .data must be more than .left->data and less than .right->data.

typedef struct node {
  int data;
  struct node *left;
  struct node *right;
} TreeNode, *Root;

Functions

// Creates a new TreeNode with data
TreeNode createNode(int data) {
  TreeNode *newNode = malloc(sizeof(TreeNode));
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Finds the sum of all the data members of a Root 
int sum(Root root) {
  if (root == NULL) {
    return 0;
  }

  return root->data + sum(root->left) + sum(root->right);
}

// Inserts a node in its proper position
void insert(Root *node, int data) {
  if (*node == NULL) {
    *node = createNode(data);
  } else if (data < (*node)->elem) {
    insert(&(*node)->LC, data);
  } else {
    insert(&(*node)->RC, data);
  }
}

// Searches the tree for a target element
bool isMember(Node root, int target) {
  if (root != NULL && target < root->elem) {
    return isMember(root->LC, target);
  } else if (root != NULL && target > root->elem) {
    return isMember(root->RC, target);
  } else {
    return root == NULL ? false : true;
  }
}

bool isMemberIterative(Node root, int target) {
  while (root != NULL && root->elem != target) {
    if (target < root->elem) {
      root = root->LC;
    } else {
      root = root->RC;
    }
  }

  return root == NULL ? false : true;
}

void delete(Node *root, int target) {
  // first traverse to the node toDelete while keeping track of parent node
  Node *trav;
  for (trav = root; *trav != NULL && (*trav)->elem != target;) {
    trav = (target < (*trav)->elem) ? &(*trav)->LC : &(*trav)->RC;
  }

  // trav is the node to delete
  if (*trav != NULL) {

    // node has two children
    // SO, we swap the min((*trav)->RC) value with the node to delete
    if ((*trav)->LC != NULL && (*trav)->RC != NULL) {
      Node *min;
      for (min = &(*trav)->RC; (*min)->LC != NULL; min = &(*min)->LC) {
        // we are traversing until we reach the leaf node
      }

      // swap min value with node to delete
      (*trav)->elem = (*min)->elem;

      // free the min node
      Node tmp = *min;
      *min = NULL;
      free(tmp);
    }

    // node to delete is a leaf node
    // SO, just make parent point to NULL
    else if ((*trav)->LC == NULL && (*trav)->RC == NULL) {
      Node tmp = *trav;
      *trav = NULL;
      free(tmp);
    }

    // node to delete has one child
    // SO, we let parent point to that child and then free the deleted node
    else {
      Node tmp = *trav;
      *trav = (*trav)->LC != NULL ? (*trav)->LC : (*trav)->RC;
      free(tmp);
    }
  }
}

References