Question

A complete binary tree is represented using array.For a node whose
position is k,its right child
can be found at which position?(The array index starts from 1)​

Answer 1

Answer

2K+1

Right child of a node can be found at 2K+1 th position

Answer 2

A complete binary tree is represented using array. For a node whose

position is k,its right child can be found at which position.

• Start filling up the components in the implementation from index 1, not index 0.
• Fill the array in the order that a level order traversal of the supplied tree would occur. The left child of the node at index I should be located at index '2i' and the right child at '2i + 1'.
• We can choose the kth element from a search tree by using an indexed binary search tree. Imagine that there were n elements in an ordered array. In a fixed amount of time, we could find the kth element. We lose this feature when using a standard binary search tree, but with a little creativity, we can get it back by using an index binary search tree. The kth element is merely different in that it takes log n to discover it.
• An indexed binary search tree does this by keeping track of the number of nodes in each subtree at the root of each subtree. As an illustration, consider a node x that has 10 nodes in its subtree, with 5 nodes each in the left and right subtrees.

#SPJ2