Question

Some questions about Binary Tree's

1. What a binary search tree is and what its advantages/disadvantages are?
2. What trees and binary trees are?
3. How data is inserted into a binary tree?
4. What full and complete binary trees look like?
5. How to perform pre, in, and post-order traversals of a tree?

Answer 1

1.BINARY SEARCH TREE:

A binary search tree is a binary tree which is either empty or satisfies the following rules:

i)The value of key in the left child or left sub-tree is less than the value of root.

ii) The value of key in the right child or right sub-tree is more than or equal to the value of root.

iii)All the sub-trees of the left and right children, follow the above two rules.

ADVANTAGES:

i)Binary Search Tree is fast in insertion and deletion etc. when balanced.

ii) Very efficient and its code is easier than other data structures.

iii) Stores keys in the nodes in a way that searching, insertion and deletion can be done efficiently.

DISADVANTAGES:

i)The shape of the binary search tree totally depends on the order of insertions, and it can be degenerated.

ii)When inserting or searching for an element in binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found, i.e., it takes a long time to search an element in a binary.

2. TREE:

A tree is a non-primitive, non-linear data structure in which items are arranged in a sorted sequence. It is used to represent hierarchical relationship existing among several data items.

BINARY TREE:

A binary tree is a finite set of data items which is either empty or consists of a single item called the root and two disjoint binary trees called the left sub-tree and right sub-tree.

In a binary tree, the maximum degree of any node is atmost 2.

3.

For insertion in binary tree you will have to follow the given conditions:

· If a node in the binary tree does not have its left child, then insert the given node (the one that we have to insert) as its left child.

· If a node in the binary tree does not have its right child then insert the given node as its right child.

· If the above-given conditions do not apply then search for the node which does not have a child at all and insert the given node there.

4.

A full binary tree is a tree in which every node other than the leaves has two children.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

5.

PREORDER TRAVERSAL:

The preorder traversal of non-empty binary tree is defined as follows:

i)Visit the root node.

ii)traverse the left sub-tree in preorder.

iii)traverse the right sub-tree in preorder.

INORDER TRAVERSAL:

The inorder traversal of non-empty binary tree is defined as follows:

i)traverse the left sub-tree in inorder.

ii) Visit the root node.

iii) traverse the right sub-tree in inorder.

POSTORDER TRAVERSAL:

The postorder traversal of non-empty binary tree is defined as follows:

i)traverse the left sub-tree in postorder.

ii)traverse the right sub-tree in postorder.

iii)Visit the root node.