## Microsoft Interview Question

SDE-2s**Country:**United States

do zig-zag breadth first search and connect right or left at each level

```
import random as rd
K = 2
k_bckup = K
''' it means we will first connect current node to the left node and then vice versa'''
left = 1
class node:
def __init__(self, data):
self.data = data
self.l = None
self.r = None
self.n = None
self.next = None
class tree:
def __init__(self):
self.root = None
def get_root(self):
return self.root
def add_node(self, node):
if (self.root == None):
self.root = node
else:
self.__add_node(self.root, node)
def __add_node(self, root, node):
if (node.data < root.data):
if (root.l != None):
self.__add_node(root.l, node)
else:
root.l = node
else:
if (root.r != None):
self.__add_node(root.r, node)
else:
root.r = node
def printTree(self):
if self.root != None:
return self._printTree(self.root)
def _printTree(self, node):
if node != None:
self._printTree(node.l)
print(node.data)
self._printTree(node.r)
def printNext(self):
if self.root != None:
return self._printNext(self.root)
def _printNext(self, node):
if node != None:
self._printNext(node.l)
if node.next != None:
print(node.data, "->", node.next.data)
self._printNext(node.r)
def insert(q, node):
if node != None and node.l != None:
q.append(node.l)
if node != None and node.r != None:
q.append(node.r)
i = tree()
print("adding data to the tree")
for j in range(0, 10):
number = rd.randint(0, 100)
print(number)
i.add_node(node(number))
print("printing inorder tree")
i.printTree()
print("debug")
q = []
q.append(i.get_root())
while len(q) > 0:
size = len(q)
prev = None
if K == 0:
K = k_bckup
K -= 1
if left == 0:
q.sort(key=lambda x:x.data)
q.reverse()
while size:
temp1 = q.pop(0)
insert(q, temp1)
size -= 1
if prev != None:
prev.next = temp1
if size == 0:
break
temp2 = q.pop(0)
insert(q, temp2)
size -=1
if K == 0:
temp1.next = temp2
temp2.next = None
prev = temp2
left = not left
print("next printing")
i.printNext()
```

do zig-zag breadth first search and connect right or left at each level

- Anonymous November 27, 2015