Startup | Phone Screen | Stretch Binary Tree by Stretching Factor K
ancientCoder
1169
Phone ScreeningInterview

Replace the nodes of a binary tree with 'k' nodes of 1/k of N original node's value. The replaced node(s) of N should extend from their parent in the same direction that N extends from its parent. Root node is a special case and treat its streched clones by extending towards the left. Must use recursion with optimal solution.

  1. Is this a medium or a hard question?
  2. Is there a way to optimize my solution further?
  3. Can the solution made be more elegant (avoid the string "left" and "right")
  4. Comment, Critic the solution :)
def stretch(root: TreeNode, k: int):
    def stretchChildren (root, k):
        if root is None:
            return
        
        stretchChildren(root.left, k) 
        stretchChildren(root.right, k)
        
        # Find if the left Node's children are leaf nodes
        if root.left: 
            stretchByKNodes(root.left, k, "left")

        # Find if the right Node's children are leaf nodes
        if root.right: 
            stretchByKNodes(root.right, k, "right")

    stretchChildren(root, k)
    # stretch root as a special case
    stretchByKNodes(root, k, "left")


def stretchByKNodes(root: TreeNode, k: int, direction: str) -> TreeNode:
    if direction == "left":
        treeRootLeft = root.left
    else:
        treeRootRight = root.right
    stretchVal = root.val // k
    root.val = stretchVal
    for _ in range(k-1):
        if(direction == "left"):
            root.left = TreeNode(stretchVal)
            root = root.left
        if(direction == "right"):
            root.right = TreeNode(stretchVal)
            root = root.right
    
    # re-attach the children from the original tree after stretching
    if direction == "left":
        root.left = treeRootLeft
    if direction == "right":
        root.right = treeRootRight

# Test Case
root = TreeNode(90)
root.left = TreeNode(60)
root.right = TreeNode(18)
root.right.right = TreeNode(12)
root.right.right.right = TreeNode(9)
root.left.left = TreeNode(45)
root.left.right = TreeNode(30)
root.left.right.left = TreeNode(19)

stretch(root. 3)

Test Case: Original tree on the left and after stretching when k = 2 or when k = 3.

image

Comments (9)