# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class CBTInserter(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self._root = root

    def insert(self, v):
        """
        :type v: int
        :rtype: int
        """
        node = TreeNode(v)
        que = [self._root]
        while que:
            cur = que.pop(0)
            if cur.left and cur.right:
                que.append(cur.left)
                que.append(cur.right)
            elif cur.left:
                que.append(cur.left)
                cur.right = node
                return cur.val
            else:
                cur.left = node
                return cur.val

    def get_root(self):
        """
        :rtype: TreeNode
        """
        return self._root

# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(v)
# param_2 = obj.get_root()
