# Worse case O(n^2) and O(nlogn) in average using binary tree travel

• The main idea is as follows:

1. Sort the array with `h` descending and if the height equal sorted with `k` ascending.
2. Building the binary tree as following rules:
2.1 using the first sorted people as root
2.2 iterate insert the people.
if the `k` of current people less than the root, insert the people in the left node, and increase the root with 1. It means that how many people preceding the root when doing inorder travel.
Otherwise, insert the node to the right. At the same time, you need to decrease the node `k` with `k-root.val` which means the preceding already has k in the left subtree.
3. Inorder travel the tree to get the final result.

NOTE: For the sort, why we should sort the value with same height in ascending? if not, the node with same height can't order correctly. It's possible that the node with less `k`(height count) could be preceding the node with more `k`. EX: `(5,3), (5,2)`. The `(5,3)` could be preceding `(5,2)`.

``````class Node(object):
def __init__(self,p):
"""
For general programming, it's better to create Person class.
"""
self.person=p
self.hcnt=1
self.left=None
self.right=None

class Solution(object):
def reconstructQueue(self,people):
if not people:
return []
# sort the people with height descending
# if height equal sort with hcnt ascending
people.sort(cmp=lambda x,y:y[0]-x[0] if x[0]!=y[0] else x[1]-y[1])
root=Node(people[0])
for p in people[1:]:
self.insert(root,p,p[1])
res=[]
self.inorder(root,res)
return res

def insert(self,root,p,hcnt):
# compare the height cnt with root
# if the hight count less than the root, go to the left
if hcnt<root.hcnt:
if not root.left:
root.left=Node(p)
else:
self.insert(root.left,p,hcnt)
# increase the root cnt,means number preceding in the left subtree
root.hcnt+=1
else:
if not root.right:
root.right=Node(p)
else:
# decrease the hcnt since it already has root.cnt before the left subtree
self.insert(root.right,p,hcnt-root.hcnt)

def inorder(self,root,res):
if not root:
return
self.inorder(root.left,res)
res.append(root.person)
self.inorder(root.right,res)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.