DEV Community

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

Posted on

8 3

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

AWS Security LIVE!

Join us for AWS Security LIVE!

Discover the future of cloud security. Tune in live for trends, tips, and solutions from AWS and AWS Partners.

Learn More

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!

Cloudinary image

Zoom pan, gen fill, restore, overlay, upscale, crop, resize...

Chain advanced transformations through a set of image and video APIs while optimizing assets by 90%.

Explore