Problem:
Complete Binary Tree A complete binary tree is a binary tree in which every internal node has two children and all leaves have the same depth. A binary tree in which if last level is not completely filled but all nodes (leaves) are pushed across to the left, is also (nearly) a complete binary tree. A binary heap data structure is an array that can be viewed as a nearly complete binary tree as shown in the following figure.   Each node of a nearly complete binary tree corresponds to an element of the array that stores the value in the node. An array $A$ that represents a binary heap has the heap size $H$, the number of elements in the heap, and each element of the binary heap is stored into $A[1...H]$ respectively. The root of the tree is $A[1]$, and given the index $i$ of a node, the indices of its parent $parent(i)$, left child $left(i)$, right child $right(i)$ can be computed simply by $\lfloor i / 2 \rfloor$, $2 \times i$ and $2 \times i + 1$ respectively. Write a program which reads a binary heap represented by a nearly complete binary tree, and prints properties of nodes of the binary heap in the following format: node $id$: key = $k$, parent key = $pk$, left key = $lk$, right key = $rk$, $id$, $k$, $pk$, $lk$ and $rk$ represent id (index) of the node, value of the node, value of its parent, value of its left child and value of its right child respectively. Print these properties in this order. If there are no appropriate nodes, print nothing. Input In the first line, an integer $H$, the size of the binary heap, is given. In the second line, $H$ integers which correspond to values assigned to nodes of the binary heap are given in order of node id (from $1$ to $H$). Output Print the properties of the binary heap in the above format from node $1$ to $H$ in order. Note that, the last character of each line is a single space character.  Constraints  $H \leq 250$  $-2,000,000,000 \leq$ value of a node $\leq 2,000,000,000$  Sample Input 1 5
7 8 1 2 3 Sample Output 1 node 1: key = 7, left key = 8, right key = 1, 
node 2: key = 8, parent key = 7, left key = 2, right key = 3, 
node 3: key = 1, parent key = 7, 
node 4: key = 2, parent key = 8, 
node 5: key = 3, parent key = 8, Reference Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.

Solution (Python):
h = int(input())
l = [int(i) for i in input().split()]

for i in range(h):
    node = i + 1
    key = l[i]
    if i == 0:
        parent = None
    else:
        parent = l[(i - 1) // 2]

    if 2 * i + 1 < len(l):
        left = l[2 * i + 1]
    else:
        left = None

    if 2 * i + 2 < len(l):
        right = l[2 * i + 2]
    else:
        right = None

    s = "node {}: key = {}, ".format(node, key)
    if parent:
        s += "parent key = {}, ".format(parent)
    if left:
        s += "left key = {}, ".format(left)
    if right:
        s += "right key = {}, ".format(right)
    print(s)

Solution (Python):

"""
Created on Sat Mar  2 17:11:49 2019

@author: Yamazaki Kenichi
"""

m = int(input())
A = input().split()
A = [''] + A

class CompleteBinaryTree(object):
    def __init__(self,size):
        self.table = [-1 for i in range(size)]
        
    def p(self,u):
        return u//2
    def left(self,u):
        return u*2
    def right(self,u):
        return u*2+1
cb = CompleteBinaryTree(m)

for i in range(1,m+1):
    res = ''
    res += 'node ' + str(i)
    res += ': key = ' + A[i] + ', '
    res += 'parent key = ' + A[cb.p(i)] + ', ' if i != 1 else ''
    res += 'left key = ' + A[cb.left(i)] + ', ' if cb.left(i) <= m else ''
    res += 'right key = ' + A[cb.right(i)] + ', ' if cb.right(i) <= m else ''
    print(res)

Solution (Python):


H = int(input().rstrip())
Ai = [int(i) for i in input().rstrip().split()]

for i, a in enumerate(Ai):
    print("node " + str(i+1) + ":",end=" ")
    print("key = " + str(Ai[i]),end=", ")
    if i != 0:
        print("parent key = " + str(Ai[(i+1)//2-1]),end=", ")
    if 2*(i+1) <= H:
        print("left key = " + str(Ai[2*(i+1)-1]),end=", ")
    if 2*(i+1) + 1 <= H:
        print("right key = " + str(Ai[2*(i+1)]),end=", ")
    print()

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write

err = 2 * (10**9) + 1

class Node:
    def __init__(self, k, l, r, p):
        self.key = k
        self.left = l
        self.right = r
        self.parent = p

n = int(input())
keys = list(map(int, readline().split()))

Heap = [Node(err, None, None, None) for i in range(n+1)]
for i in range(1, n+1):
    Heap[i].key = keys[i-1]
    if 2*i  < n+1:
        Heap[i].left = Heap[2*i]
    if 2*i + 1 < n+1:
        Heap[i].right = Heap[2*i + 1]
    if i > 1:
        Heap[i].parent = Heap[int(i/2)]

for i in range(1, n+1):
    write("node " + str(i) + ": key = " + str(Heap[i].key) + ", ")
    if Heap[i].parent is not None:
        write("parent key = " + str(Heap[i].parent.key) + ", ")
    if Heap[i].left is not None:
        write("left key = " + str(Heap[i].left.key) + ", ")
        if Heap[i].right is not None:
            write("right key = " + str(Heap[i].right.key) + ", ")
    write("\n")

Solution (Python):
import sys
import math

_n = int(input())
heap = [int(i) for i in input().split()]
heap.insert(0, -sys.maxsize)

for ix, key in enumerate(heap):
    if ix == 0:
        continue

    p_ix = math.floor(ix / 2)
    p_key = heap[p_ix] if p_ix > 0 else sys.maxsize
    l_ix = ix * 2
    l_key = heap[ix * 2] if l_ix < len(heap) else sys.maxsize
    r_ix = ix * 2 + 1
    r_key = heap[ix * 2 + 1] if r_ix < len(heap) else sys.maxsize
    print(f'node {ix}: ', end='')
    print(f'key = {key}, ', end='')
    if p_ix != 0:
        print(f'parent key = {p_key}, ', end='')
    if l_ix < len(heap):
        print(f'left key = {l_key}, ', end='')
    if r_ix < len(heap):
        print(f'right key = {r_key}, ', end='')
    print()

Solution (Python):
def printHeap(H,Q,n):
    if H+1 == n:
        return
    print("node",n,end=": ")
    print("key =",Q[n],end=", ")
    print("parent key =",Q[int(n/2)],end=", ") if 1<n else None
    print("left key =",Q[2*n],end=", ") if 2*n<=H else None
    print("right key =",Q[2*n+1],end=", ") if 2*n+1<=H else None
    print()
    printHeap(H,Q,n+1)
    



H = int(input())
Q = list(map(int, input().split()))
Q.insert(0,-1)
printHeap(H,Q,1)

Solution (Python):
H = int(input())
A = list(map(int, input().split()))

def per(p):
    global parentkey
    if p%2 == 0:
        pk = p/2-1
    else:
        pk = p//2
    if pk >= 0:
        parentkey = 'parent key = {}, '.format(A[int(pk)])
    else:
        parentkey = ''


def left(l):
    l += 1
    global leftkey
    if 2*l <= H:
        leftkey = 'left key = {}, '.format(A[2*l-1])
    else:
        leftkey = ''


def right(r):
    r += 1
    global rightkey
    if 2*r+1 <= H:
        rightkey = 'right key = {}, '.format(A[2*r])
    else:
        rightkey = ''


for i in range(H):
    per(i)
    left(i)
    right(i)
    print('node {}: key = {}, {}{}{}'.format(i+1, A[i], parentkey, leftkey, rightkey))

Solution (Python):




import sys
input = sys.stdin.readline
import cProfile

def showHeap(li):
    
    for i in range(1,len(li)+1):
        n1=n2=n3=n4 =""
        p = i // 2
        r = i * 2 + 1
        l = i * 2
 
        n1 = "node {}: key = {}, ".format(str(i) , str(li[i-1]))
        if p > 0:
            n2 = "parent key = {}, ".format(li[p-1])
        if l -1 < len(li): 
            n3 = "left key = {}, ".format(li[l-1])
        if r -1 < len(li): 
            n4 = "right key = {}, ".format(li[r-1])
        
        print (n1+n2+n3+n4)
            
def main():
    n = int(input())
    l = list(map(int,input().split()))
    showHeap(l)

        
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def parent(i):
    return int(i/2)

def left(i):
    return 2 * i

def right(i):
    return (2 * i) + 1

if __name__ == "__main__":
    n = int(input())
    node = [None]
    node.extend(list(map(int, input().split())))
    for i in range(1,n+1):
        sys.stdout.write("node {}: key = {}, ".format(i, node[i])) 
        p = parent(i)
        if 0 < p <= n:
            sys.stdout.write("parent key = " + str(node[p]) + ", ")
        l = left(i)
        if 0 < l <= n:
            sys.stdout.write("left key = " + str(node[l]) + ", ")
        r = right(i)
        if 0 < r <= n:
            sys.stdout.write("right key = " + str(node[r]) + ", ")
        sys.stdout.write("\n")

Solution (Python):
def main():
    num_node = int(input())
    nodes = [int(x) for x in input().split()]

    for i in range(num_node):
        idx = i + 1
        print("node {}: key = {}, ".format(idx, nodes[i]), end="")
        
        parent_idx = idx // 2
        if parent_idx != 0:
            print("parent key = {}, ".format(nodes[parent_idx-1]), end="")
        
        left_idx = idx * 2
        if left_idx <= num_node:
            print("left key = {}, ".format(nodes[left_idx-1]), end="")
        
        right_idx = idx * 2 + 1
        if right_idx <= num_node:
            print('right key = {}, '.format(nodes[right_idx-1]), end="")
        print("")
    return


main()

Solution (Python):
import sys
n = int(sys.stdin.readline())
h = list(map(int,sys.stdin.readline().split()))

for i in range(n):
    print('node {0}: key = {1}, '.format(i+1, h[i]), end='')
    if (i+1)//2-1>=0:
        print('parent key = {0}, '.format(h[(i+1)//2-1]), end='')

    if (i+1)*2<n+1:
        print('left key = {0}, '.format(h[(i+1)*2-1]), end='')

    if (i+1)*2<n:
        print('right key = {0}, '.format(h[(i+1)*2]), end='')

    print()

Solution (Python):





n=int(input())


tree=input().split()
tree.insert(0,"error")

for i in range(1,n+1):
    print(f"node {i}: key = {tree[i]}, ",end="")
    if(i!=1):
        print(f"parent key = {tree[i//2]}, ",end="")
    try:
        print(f"left key = {tree[2*i]}, ",end="")
    except:
        print()
        continue
    try:
        print(f"right key = {tree[2*i + 1]}, ")
    except:
        print()

Solution (Python):
N = int(input())
*A, = map(int, input().split())
for i in range(N):
    R = ["node %d: key = %d," % (i+1, A[i])]
    l = 2*i+1; r = 2*i+2
    if i:
        R.append("parent key = %d," % A[(i-1)//2])
    if l < N:
        R.append("left key = %d," % A[l])
    if r < N:
        R.append("right key = %d," % A[r])
    print(*R, "")

Solution (Python):
import math

H = int(input())
A = [None] + list(map(int, input().split()))
for i in range(1, H+1):
    print(f"node {i}: key = {A[i]}, " 
          + (f"parent key = {A[math.floor(i/2)]}, " if (math.floor(i/2) >= 1) else "")
          + (f"left key = {A[2*i]}, " if 2*i <= H else "")
          + (f"right key = {A[2*i+1]}, " if (2*i + 1) <= H else "")
          )

Solution (Python):
from math import floor


def parent_node(k):
    return k // 2


def left_node(k):
    return 2 * k


def right_node(k):
    return 2 * k + 1


def main():
    H = int(input())
    elems = [0] + [int(x) for x in input().split()]

    for k in range(1, H + 1):
        print("node {}: ".format(k), end="")
        print("key = {}, ".format(elems[k]), end="")
        if parent_node(k) >= 1:
            print("parent key = {}, ".format(
                elems[parent_node(k)]), end="")
        if left_node(k) <= H:
            print("left key = {}, ".format(
                elems[left_node(k)]), end="")
        if right_node(k) <= H:
            print("right key = {}, ".format(
                elems[right_node(k)]), end="")
        print()


main()

Solution (Python):
class Node(object):
    def __init__(self, key=None, parent=None, left=None, right=None):
        self.parent = parent
        self.left = left
        self.right = right

def print_nodes(nodes, n):    
    for i in range(1, n+1):
        p = "parent key = {}, ".format(nodes[i].parent)
        l = "left key = {}, ".format(nodes[i].left)
        r = "right key = {}, ".format(nodes[i].right)
        if nodes[i].parent == None:
            p = ""
        if nodes[i].left == None:
            l = ""
        if nodes[i].right == None:
            r = ""
        print("node {0}: key = {1}, {2}{3}{4}".format(i, nodes[i].key, p, l, r))

n = int(input())
A = [int(i) for i in input().split()]
A.insert(0, None)
nodes = [Node() for _ in range(n+1)]
for i in range(1, n+1):
    nodes[i].key = A[i]
    if 2*i < n+1:
        nodes[i].left = A[2*i]
    if 2*i+1 < n+1:
        nodes[i].right = A[2*i+1]
    if i == 1:
        pass
    else:
        nodes[i].parent = A[i >> 1]

print_nodes(nodes, n)

Solution (Python):
txt1 = "node {}: key = {}, "
txt2 = "parent key = {}, "
txt3 = "left key = {}, "
txt4 = "right key = {}, "

H = int(input())
A = [int(i) for i in input().split()]
A = [0] + A
for i,j in enumerate(A):
    if i==0:
        continue
    tmp = txt1.format(i, j)
    if not i == 1:
        tmp+=txt2.format(A[i//2])
    if 2*i <= H:
        tmp+=txt3.format(A[2*i])
    if 2*i+1 <= H:
        tmp+=txt4.format(A[2*i+1])
    print(tmp)

Solution (Python):
def parent(i):
    return i // 2


def left(i):
    return i * 2


def right(i):
    return i * 2 + 1


h = int(input())
a = [-1]
a.extend([int(v) for v in input().split()])

for i in range(1, h+1):
    result = 'node {0}: key = {1}, '.format(i, a[i])
    if parent(i) >= 1:
        result += 'parent key = {0}, '.format(a[parent(i)])
    if left(i) <= h:
        result += 'left key = {0}, '.format(a[left(i)])
    if right(i) <= h:
        result += 'right key = {0}, '.format(a[right(i)])
    print(result)

Solution (Python):
class Node:
	def __init__(self, i, k):
		self.i = i
		self.k = k
		self.p = self.l = self.r = None
		
	def __str__(self):
		ret = 'node ' + str(self.i) + ': '
		ret += 'key = ' + str(self.k) + ', '
		if self.p != None:
			ret += 'parent key = ' + str(self.p) + ', '
		if self.l != None:
			ret += 'left key = ' + str(self.l) + ', '
		if self.r != None:
			ret += 'right key = ' + str(self.r) + ', '
		return ret

n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	id = i + 1
	node = Node(id, a[id-1])
	if i != 0:
		p = int(id/2) - 1
		node.p = a[p]
	l = id*2-1
	r = id*2
	if l < n:
		node.l = a[l]
	if r < n:
		node.r = a[r]		
	print(node)

Solution (Python):

class Node:
    def __init__(self, key):
        self.key = key


from math import floor
H = int(input())
heap = [None]*(H+1)
for i,k in enumerate(input().split()):
    heap[i+1] = Node(k)

for i,h in enumerate(heap):
    if i == 0: continue
    print('node {0}: key = {1}, '.format(i, h.key), end='')
    p_id = floor(i/2)
    if p_id > 0:
        print('parent key = {0}, '.format(heap[p_id].key), end='')
    l_id = 2 * i
    if 0 < l_id < len(heap):
        print('left key = {0}, '.format(heap[l_id].key), end='')
    r_id = 2 * i + 1
    if 0 < r_id < len(heap):
        print('right key = {0}, '.format(heap[r_id].key), end='')
    print()