**Binary Search tree in Cpp(BST) with examples:**

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element.

The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees”.

**Empty tree:**A null pointer represents a binary tree with no elements -- the empty tree.

The formal recursive definition is: a binary tree is either empty, or is made of a single node,

Where the left and right pointers (recursive definition ahead) each point to a binary tree.

They differentiate only with one feature that is the organization of the data.

Here is the small example that helps us to understand the binary tree

A

**binary tree**is a tree that is limited such that each node has only two children.

Binary Tree |

**Definitions:**

If n1 is the root of a binary tree and n2 is the root of its left or right tree, then n1 is the parent of n2 and n2 is the left of n1.

A node that has no children is called a leaf, here the leaf nodes are n4, n5, n6

The nodes are siblings if they are left and right children of the same parent.

The level of a node in a binary tree:

The root of the tree has level 0

The level of any other node in the tree is one more than the level of its parent.

Structure of the binary tree:

root = NULL; // empty tree

Each node of a binary tree has both left and right sub trees which can be reached with pointers:

Struct T_node{ int data; struct T_node *stL_child; struct T_node *stR_child; };

**Binary Trees Traversal:**

Three are three possible tree traversals orderings available, those are shown below:

•Preorder•Inorder•Postorder

These names are chosen according to the step at which the root node is visited.

**Preorder traversal:**

The node is visited before its left and right sub trees.

**Inorder traversal:**

The root is visited first between the subt rees.

**Post order traversal:**

The root is visited last after both sub trees.

**Example:**

**4**

**/ \**

**2 5**

**/ \**

**1 3**

Produces the output "1 2 3 4 5". This is known as an "inorder" traversal of the tree.

Preorder: 4 2 1 5 3 Inorder: 1 2 3 4 5 Postorder: 1 3 2 5 4

**Finding the maximum value in a binary tree:**

Compute the "maxDepth" of a tree -- the number of nodes along

the longest path from the root node down to the farthest leaf node.

int FindMaxDepth(struct node* stNode) { if (stNode==NULL) { return(0); } else { // compute the depth of each subtree int lDepth = FindMaxDepth(stNode->left); int rDepth = FindMaxDepth(stNode->right); // use the larger one if (lDepth > rDepth) return(lDepth + 1); else return(rDepth + 1); } }

**How to add all values in a Binary Tree:**

int add(struct node* stNode) { if (stNode == NULL) return 0; else return (stNode ->data + add(stNode ->left_child)+ add(stNode ->right_child)); }

## No comments:

Post a Comment