How to convert from recursive function to non recursive?

Question

How can I convert the following recursive code to a non recursive code?

In particular, I am looking at the last 2 line of code. I hope I am able to get help or clue as I am currently totally clueless.

def newNode(data):
    return node(data)
  
# Function to print Leaf Nodes at
# a given level
def PrintLeafNodes(root, level):
    if (root == None):
        return
  
    if (level == 1):
        if (root.left == None and
            root.right == None):
            print(root.data, end = " ")
     
    elif (level > 1):
        PrintLeafNodes(root.left, level - 1) #convert from recursive to non recursive
        PrintLeafNodes(root.right, level - 1) #convert from recursive to non recursive

Instead of calling the method itself again (= recursive) you save the values in some variables and make a while loop and don't call the method again. — Tin Nguyen
– Tin Nguyen, Commented Oct 27, 2020 at 12:09
You should show your attempt of converting that code and ask if something specific in the process went wrong, not ask for the solution. This is not a code service — Tomerikoo
– Tomerikoo, Commented Oct 27, 2020 at 12:26

metehan · Accepted Answer · 2020-10-27 12:29:17Z

You can change and adapt your code by visiting this website. Also I tried to adapt the code for you.

def PrintLeafNodes(root): 
      
    # Set current to root of binary tree 
    current = root  
    stack = [] # initialize stack 
    done = 0 
      
    while True: 
          
        # Reach the left most Node of the current Node 
        if current is not None: 
              
            # Place pointer to a tree node on the stack  
            # before traversing the node's left subtree 
            stack.append(current) 
          
            current = current.left  
  
          
        # BackTrack from the empty subtree and visit the Node 
        # at the top of the stack; however, if the stack is  
        # empty you are done 
        elif(stack): 
            current = stack.pop() 
            print(current.data, end=" ") # Python 3 printing 
          
            # We have visited the node and its left  
            # subtree. Now, it's right subtree's turn 
            current = current.right  
  
        else: 
            break
       
    print(current.data, end = " ")

Collectives™ on Stack Overflow

How to convert from recursive function to non recursive?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related