In continuation of my previous blog, Brushing up C, data structures, we’ll be taking up *Binary Trees *.

**1. Terminology**

- Tree: A non-linear, hierarchical structure is called a tree. Linked list is linear, a family tree ( a representation of family members and their generations) is non linear.
- Binary tree: A tree, where there is a parent, who has
*two *children is called a binary tree.
- Binary Search Tree: A binary tree, where the value of left child is less than parent value and the value of right child is more than the parent value, is called binary search tree.
- Root: The topmost or the first node of the tree is root.
- Parent node: The node having children.
- Child node: The child of a parent node. The parent node has a pointer to the child node.
- Leaf node: A node that doesn’t have any child is leaf node.

**2. Why trees?**

Sometimes, we want to arrange data in hierarchical manner, trees are a better choice in those cases.

Search operations on Binary Search Trees are more efficient than linked lists. We can insert and delete elements in good time.

**3. Tree traversals**

Unlike linked lists (which can traversed only linearly), trees can be travesed in many different ways.

- In order: The sequence of traversal is left child, root, right child.
- Pre order: Here, the root is processed first, then the left child and then the right child.
- Post order: As is evident by now, left child first, then right child and then finally the parent node .

**4. Implementation**

The basic structure for a tree node can be defined as:

*struct treenode*

*{*

*int data;*

*struct treenode *leftChild;*

*struct treenode *rightChild;*

*};*

A new node can be dynamically allocated for a new entry.

*Struct treenode * root = (struct treenode *)malloc(sizeof(struct treenode));*

Root node can be initialised as:

*root->data = someValue;*

*root->leftChild = NULL;*

*root->rightChild = NULL;*

When adding a child, create a new node.

Assign the parent’s leftChild/rightChild to the new node.

*Struct treenode *newNode= **(struct treenode *)malloc(sizeof(struct treenode));*

*root->leftChild = newNode; *

*Or*

*root->rightChild = newNode;*

depending on if new data value is less than or more than root data value.

The search operations are generally *recursive*, as the nodes are recursively searched till a leaf or match is found.

**Summary**

Friends, here I end my series Brushing up C . I hope you enjoyed it, and got to learn along ☺️ .

I will be starting my next tutorial series on **C++.** Please be a part of it ☺️ .

### Like this:

Like Loading...

*Related*