DEV Community 👩‍💻👨‍💻

Cover image for Today I Learned: BST Traversal
Anzhari Purnomo
Anzhari Purnomo

Posted on

Today I Learned: BST Traversal

Problem Statement

Write three functions (in-order, pre-order, and post-order traversal) that takes in a Binary Search Tree (BST) and an empty array, traverse the BST add the node's value to the input array and return the array.

Sample Input

tree =        10
           /       \
         5          15
      /    \           \
    2       5           22
  /
1
Enter fullscreen mode Exit fullscreen mode

Sample Result

in_order = [1, 2, 5, 5, 10, 15, 22]
pre_order = [10, 5, 2, 1, 5, 15, 22]
post_order = [1, 2, 5, 5, 22, 15, 10]
Enter fullscreen mode Exit fullscreen mode

Code

def in_order_traversal(tree, array):
    if tree is not None: 
        in_order_traversal(tree.left, array)
        array.append(tree.value)
        in_order_traversal(tree.right, array)
    return array


def pre_order_traversal(tree, array):
    if tree is not None: 
        array.append(tree.value)
        pre_order_traversal(tree.left, array)
        pre_order_traversal(tree.right, array)
    return array


def post_order_traversal(tree, array):
    if tree is not None: 
        post_order_traversal(tree.left, array)
        post_order_traversal(tree.right, array)
        array.append(tree.value)
    return array
Enter fullscreen mode Exit fullscreen mode

Notes

  • N/A

Credits

  • Algoexpert for the problem statement
  • XKCD for the cover image

Top comments (2)

Collapse
 
qm3ster profile image
Mihail Malo

Could you plese write ```python for the last code block?

Collapse
 
anzhari profile image
Anzhari Purnomo

Ahhh, I see. The code looks better now. Thanks for the heads up!

Join us at DEV
Yes, this is technically an “ad”, but really we just want to ask if you want to join DEV. We have 900k+ developers reading, posting, and enjoying community, and would love to have you.   Create an account and continue your coding journey.