Here is a solution that takes running time O(N) where N is the number of elements in Binary Tree class BSTNode: def __init__(self,key): self.key = key self.parent = None self.left = None self.right = None def insert(self,node): if node.key self.key: if self.right: self.right.insert(node) else: self.right = node node.parent = self def capture_level_nodes(self): main_list = [[self]] parents = [self] while parents: children = [] for parent in parents: if parent.left: children.append(parent.left) if parent.right: children.append(parent.right) if children: main_list.append(children) parents = children for level in main_list: for elem in level: if elem.parent: print elem.key,"(",elem.parent.key,")", else: print elem.key, "( None ) ", print a = BSTNode(8) a.insert(BSTNode(5)) a.insert(BSTNode(2)) a.insert(BSTNode(3)) a.insert(BSTNode(7)) a.insert(BSTNode(4)) a.insert(BSTNode(9)) a.insert(BSTNode(1)) a.insert(BSTNode(6)) a.capture_level_nodes()