CODEWITHSUNDEEP
python
Beginner
Beginner

Reputation: 19

Traverse through binary tree to change the value of each nodes?

I'm trying to transverse through a binary tree to add "newvalue" to each nodes current value.

def(node, 2):

Before:

      1
     / \
    2   3
   /\   /
  5  6  7

After:

      3
     /\
    4  5
   /\  /
  7  8 9

How should I approach this recursively?!

Upvotes: 0

Views: 3763

Answers (2)

Ashwin Balamohan
Ashwin Balamohan

Reputation: 3332

Harold provided a very clean and general example. Here's a take, with annotations, that will work for a binary tree

With a recursive algorithm, you've got to think of two things: 1. The base case 2. The recursive call

In your example: - Base case = Node has no children. No recursive calls will take place - Recursive call = Each node is its own mini-tree, so call the function on each child

def increase_tree_values(node, delta):
    """ Increases/decreases the value of all nodes in the tree by the value 'delta'
    """

    # increase the current node's value
    node.value += delta

    # recursively call function on left child, if it exists
    if node.left_child:
        increase_tree_values(node.left_child, delta)

    # recursively call function on right child, if it exists
    if node.right_child:
        increase_tree_values(node.right_child, delta)



# presuming you have some binary tree called 'tree' already constructed
# increase all nodes in 'tree' by 2
increase_tree_values(tree, 2)

Let me know if you have any questions. If this exercise was presented to you in school, they're really just trying to get you to identify this as a simple tree traversal, where you change the value of the nodes as you traverse through the tree. What I would recommend is for you to try your hand at programming all the different tree traversals without any notes. You'll learn a lot about trees and recursion that way.

Upvotes: 2

gukoff
gukoff

Reputation: 2240

def add_value(node, delta):
    node.value += delta
    for child in node.children:
        add_value(child, delta)

Upvotes: 1

Related Questions