Hi, here’s your problem today. This problem was recently asked by Google:
Given a binary tree, remove the nodes in which there is only 1 child, so that the binary tree is a full binary tree.
So leaf nodes with no children should be kept, and nodes with 2 children should be kept as well.
Here’s a starting point:
from collections import deque class Node(object): def __init__(self, value, left=None, right=None): self.left = left self.right = right self.value = value def __str__(self): q = deque() q.append(self) result = '' while len(q): num = len(q) while num > 0: n = q.popleft() result += str(n.value) if n.left: q.append(n.left) if n.right: q.append(n.right) num = num - 1 if len(q): result += "\n" return result def fullBinaryTree(node): # Fill this in. # Given this tree: # 1 # / \ # 2 3 # / / \ # 0 9 4 # We want a tree like: # 1 # / \ # 0 3 # / \ # 9 4 tree = Node(1) tree.left = Node(2) tree.right = Node(3) tree.right.right = Node(4) tree.right.left = Node(9) tree.left.left = Node(0) print fullBinaryTree(tree) # 1 # 03 # 94