CODEWITHSUNDEEP
pythonalgorithmtreebinary-search-treetraversal
crystyxn
crystyxn

Reputation: 1601

list index out of range - pre-order traversal of BST

I am trying to pre-order traverse a BST that I get in the form of an array: enter image description here

example input: ["5","2","6","1","9","#","8","#","#","#","#","4","#"] where # is an absent node in the tree

My output should be the result of the pre-order traversal:

5 2 1 9 6 8 4

So far I have been successful, except for the very last node, I get index out of range. Here is my code so far:

 def traverse(strArr):
  strArr.insert(0, '#')

  def preorder(arr, ind):
    if ind <= len(arr) and arr[ind] != '#':
      print(arr[ind])
      preorder(arr, 2*ind)
      preorder(arr, 2*ind+1)

  preorder(strArr, 1)

traverse(["5","2","6","1","9","#","8","#","#","#","#","4","#"])

What do I need to change in order for the last node (4 in this case) to show without errors?

Upvotes: 0

Views: 234

Answers (1)

Don Foumare
Don Foumare

Reputation: 464

Well there are two issues.

  1. Arrays are zero-based: if ind <= len(arr) and arr[ind] != '#': allows ind to become len(arr) which is larger than the index of the last element of arr. In the same line you use ind as an index to access the array arr[ind], which results in an IndexError. The fix here is to check if ind is less than len(arr):
if ind < len(arr) and arr[ind] != '#':
  1. The 4 is at the wrong index: It is currently at index 11 but should be at index 13. Fix here:
traverse(["5","2","6","1","9","#","8","#","#","#","#","#","#","4","#"])

Upvotes: 1

Related Questions