Binary Tree

Question 1

Define a Binary Tree

Answer 1

A normal tree has no restrictions on the number of children each node can have. A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element.

There are three different types of binary trees:

• Full binary tree: Every node other than leaf nodes has 2 child nodes.
• Complete binary tree: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible.
• Perfect binary tree: All nodes have two children and all leaves are at the same level.

Question 2

How is a Binary Heap Usually Implemented?

Answer 2

A binary heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices:

• The root element is 0
• Left child : (2*i)+1
• Right child : (2*i)+2
• Parent child : (i-1)/2

Question 3

What is a Binary Heap?

Answer 3

A Binary Heap is a Binary Tree with following properties:

• It’s a complete tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.
• A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

Question 4

What is a Binary Search Tree?

Answer 4

Binary search tree is a data structure that quickly allows maintaining a sorted list of numbers.

• It is called a binary tree because each tree node has a maximum of two children.
• It is called a search tree because it can be used to search for the presence of a number in O(log n) time.

The properties that separate a binary search tree from a regular binary tree are:

• All nodes of the left subtree are less than the root node
• All nodes of the right subtree are more than the root node
• Both subtrees of each node are also BSTs i.e. they have the above two properties