Modify Binary Tree by replacing each node with nearest power of minimum of previous level

import math

  

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

  

  

def nearestPow(x, base):

    k = int(math.log(x, base))

    if abs(base**k - x) < abs(base**(k+1) - x):

        return base**k

    else:

        return base**(k+1)

  

def printLevelOrder(root):

  

    

    if root is None:

        return

  

    

    

    q = []

  

    

    q.append(root)

  

    while q:

  

        

        

        count = len(q)

  

        

        

        

        while count > 0:

            temp = q.pop(0)

            print(temp.val, end=' ')

  

            

            

            if temp.left:

                q.append(temp.left)

  

            

            

            if temp.right:

                q.append(temp.right)

  

            

            count -= 1

  

  

def replaceNodes(root):

  

    

    

    que = [root]

  

    

    lvl = 1

  

    

    

    minPrev = root.val

  

    

    

    minCurr = root.val

  

    

    while True:

  

        

        length = len(que)

  

        

        if not length:

            break

  

        

        minPrev = minCurr

        minCurr = 1000000000000000000

  

        

        while length:

  

            

            temp = que.pop(0)

  

            

            minCurr = min(temp.val, minCurr)

  

            

            

            temp.val = nearestPow(temp.val, minPrev)

  

            

            if temp.left:

  

                

                

                que.append(temp.left)

  

            

            if temp.right:

  

                

                

                que.append(temp.right)

  

            

            length -= 1

  

        

        lvl += 1

  

    

    

    printLevelOrder(root)

  

  

  

root = TreeNode(7)

root.left = TreeNode(4)

root.right = TreeNode(11)

root.left.right = TreeNode(23)

  

replaceNodes(root)

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets