I am trying to implement a parse function. "From an infix stream of tokens, and the current index into the token stream, construct and return the tree, as a collection of Nodes, that represents the expression" This is what i have came up with so far:
def parse[tokens, i = 0]:
lst = []
token = lst[i]
left, i = parse[lst, i+1]
right, i = parse[lst, i+1]
if token.isdigit[]:
return mkLiteralNode[token]
elif token.isidentifier[]:
return mkVariableNode[token]
else:
left, i = parse[lst, i+1]
right, i = parse[lst, i+1]
return True
So in general, token.isdigit means that this command has to return an integer, which is mkLiteralNode, and token.isidentifier should return variable, or mkVariableNode. I am getting an error when testing this function and the error is:
token = lst[i]
TypeError: 'int' object is not subscriptable
How can i fix this?
View the Desktop Version
Given a sorted list nums of size n, construct a binary search tree by
- Taking nums[k] as the root where k = floor[n / 2].
- Recursively constructing the left subtree using the list nums[:k]
- Recursively constructing the right subtree using the list nums[k + 1:]
Constraints 0 ≤ n ≤ 100,000 Example 1 Input
nums = [0, 1, 2, 3, 4]
Output:
2 / \ 1 4 / / 0 3
The problem itself is recursive and we can build a recursive algorithm. First, find the middle point, build a node, and recursively build its left and right tree. Since the entire list is sorted, the binary tree we build is a Binary Search Tree.
Python algorithm to Build a Binary Search Tree:
C++ algorithm to Build a Binary Search Tree:
Both implementations are O[N^2] time where N is the number of the values in the list because at each partition, we are allocating spaces and copying over the sublists. There is O[N] space where we are implicitly requiring a stack because of using stack.
If we are using the left, right pointer to avoid the sublist copying, the time complexity will be O[N]:
–EOF [The Ultimate Computing & Technology Blog]
Product Recommendations
View the Desktop VersionRelated Posts
Write a Python program to convert a given array elements to a height balanced Binary Search Tree [BST].
Note: The selection sort improves on the bubble sort by making only one exchange for every pass through the list.
Sample Solution:
Python Code:
class TreeNode[object]: def __init__[self, x]: self.val = x self.left = None self.right = None def array_to_bst[array_nums]: if not array_nums: return None mid_num = len[array_nums]//2 node = TreeNode[array_nums[mid_num]] node.left = array_to_bst[array_nums[:mid_num]] node.right = array_to_bst[array_nums[mid_num+1:]] return node def preOrder[node]: if not node: return print[node.val] preOrder[node.left] preOrder[node.right] array_nums = [1,2,3,4,5,6,7] print["Original array:"] print[array_nums] result = array_to_bst[array_nums] print["\nArray to a height balanced BST:"] print[preOrder[result]]Sample Output:
Original array: [1, 2, 3, 4, 5, 6, 7] Array to a height balanced BST: 4 2 1 3 6 5 7 NoneFlowchart:
Python Code Editor:
Contribute your code and comments through Disqus.
Previous: Write a
Python program to delete a node with the given key in a given Binary search tree [BST].
Next: Write a Python program to find the kth smallest element in a given a binary search tree.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
Returns the items that are parity outliers:
Example:
from collections import Counter def find_parity_outliers[nums]: return [ x for x in nums if x % 2 != Counter[[n % 2 for n in nums]].most_common[][0][0] ] print[find_parity_outliers[[1, 2, 3, 4, 5, 6]]]Output:
[2, 4, 6]A sorted linked list is used to construct a binary tree from the leaves to the root. The idea is to insert nodes in a binary tree in the same order as they appear in the linked list so that the tree can be constructed with the time complexity of O[n]O[n]O[n].
Method
The number of nodes in the linked list are counted and set equal to n. First, the middle node is set as the root [always]. Then, the left subtree is constructed recursively, using the left n/2 nodes, and connected with the root at the end. The right subtree is similarly constructed and connected to the root.
While constructing the BST, we keep moving the list head pointer to the next node so that we have the appropriate pointer in each recursive call.
Suppose the following linked list needs to be converted into a binary tree. The following illustrations make use of the above-mentioned method to create a binary tree.
The linked list:
The converted binary tree:
The code below implements the method above.
#include using namespace std; /* Link list node */ class listNode { public: int data; listNode* next; }; /* A Binary Tree node */ class treeNode { public: int data; treeNode* left; treeNode* right; }; treeNode* newNode[int data]; int countNodesOfList[listNode *head]; treeNode* sortedListToBTrecur[listNode **head_ref, int n]; /* This function counts the number of nodes in Linked List and then calls*/ treeNode* sortedListToBST[listNode *head] { /*Count the number of nodes in Linked List */ int n = countNodesOfList[head]; return sortedListToBTrecur[&head, n]; } /* The main function that constructs balanced BT and returns root of it. head_ref --> Pointer to pointer to head node of linked list n --> No. of nodes in Linked List */ treeNode* sortedListToBTrecur[listNode **head_ref, int n] { /* Base Case */ if [n data]; root->left = left; /* Change head pointer of Linked List for parent recursive calls */ *head_ref = [*head_ref]->next; /* Recursively construct the right subtree and link it with root The number of nodes in right subtree is total nodes - nodes in left subtree - 1 [for root] which is n-n/2-1*/ root->right = sortedListToBTrecur[head_ref, n - n / 2 - 1]; return root; } /* A utility function that returns count of nodes in a given Linked List */ int countNodesOfList[listNode *head] { int count = 0; listNode *temp = head; while[temp] { temp = temp->next; count++; } return count; } /* Function to insert a node at the beginning of the linked list */ void push[listNode** head_ref, int new_data] { /* allocate node */ listNode* new_node = new listNode[]; /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = [*head_ref]; /* move the head to point to the new node */ [*head_ref] = new_node; } /* Function to print nodes in a given linked list */ void printList[listNode *node] { while[node!=NULL] { cout data next; } } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ treeNode* newNode[int data] { treeNode* node = new treeNode[]; node->data = data; node->left = NULL; node->right = NULL; return node; } /* A utility function to print preorder traversal of BT */ void preOrder[treeNode* node] { if [node == NULL] return; cout2->3->4->5->6->7 */ push[&head, 7]; push[&head, 6]; push[&head, 5]; push[&head, 4]; push[&head, 3]; push[&head, 2]; push[&head, 1]; cout