Using pre-order traversal with Polish notation
Expression trees are a kind of binary tree that represent arithmetic expressions:
By applying in-order traversal to an expression tree, you can obtain the infix notation. This notation for the given tree will be (10-5)*3.
By applying pre-order traversal to an expression tree, you can obtain the prefix notation, aka Polish notation, where the operator appears before its operands. This notation for the given tree will be *-10 5 3.
By applying post-order traversal to an expression tree, you can obtain the postfix notation, aka reverse Polish notation, where the operator appears after its operands. This notation for the given tree will be 10 5- 3*.
Code the pre-order traversal so that you can obtain the prefix notation of this expression tree.
This is a part of the course
“Data Structures and Algorithms in Python”
Exercise instructions
- Check if
current_nodeexists. - Print the value of the
current_node. - Call the
pre_order()function recursively on the appropriate halves of the tree.
Hands-on interactive exercise
Have a go at this exercise by completing this sample code.
import queue
class ExpressionTree:
def __init__(self):
self.root = None
def pre_order(self, current_node):
# Check if current_node exists
____:
# Print the value of the current_node
____
# Call pre_order recursively on the appropriate half of the tree
____
____
et = CreateExpressionTree()
et.pre_order(et.root)This exercise is part of the course
Data Structures and Algorithms in Python
Explore data structures such as linked lists, stacks, queues, hash tables, and graphs; and search and sort algorithms!
This chapter will focus on searching algorithms, like linear search, binary search, depth first search, and breadth first search. You will also study binary search trees and how to search within them.
Exercise 1: Linear Search and Binary SearchExercise 2: Implementing binary searchExercise 3: Binary search using recursionExercise 4: Binary Search Tree (BST)Exercise 5: Inserting a node into a binary search treeExercise 6: Finding the minimum node of a BSTExercise 7: Depth First Search (DFS)Exercise 8: Printing book titles in alphabetical orderExercise 9: Using pre-order traversal with Polish notationExercise 10: Implementing DFS for graphsExercise 11: Breadth First Search (BFS)Exercise 12: Using breadth first search in binary treesExercise 13: Finding a graph vertex using BFSWhat is DataCamp?
Learn the data skills you need online at your own pace—from non-coding essentials to data science and machine learning.