# Trie and Trees

## trie

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Values are normally not associated with every node, only with leaves and some inner nodes that correspond to keys of interest. For the space-optimized presentation of prefix tree, see compact prefix tree.

Trie is one of the most important data structure for autocomplete.

### Trie Problems

Various problems on Trie can be found here

### Postfix to Infix

#### Evaluate Postfix expression

Valid operators are +, -, *, /.
Each operand may be an integer or another expression.

Some examples:
 ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6 

### Tree Problems

#### Find BST is balanced or not

Balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.

#### Find Binary Tree is BST or not

A binary search tree (BST) is a node based binary tree data structure which has the following properties.
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Method 1

Perform inorder traversal on tree and store it in temporary array. By property of inorder traversal the numbers stored should be sorted sequence of it’s a BST else it’s not BST.

The only caveat is that this method require O(n) space

Method 2

#### BST - Recursive Inorder Traversal

Time complexity O(n) and space complexity is size of stack for function calls

#### BST - Iterative Inorder Traversal

Time complexity O(n) and space complexity is size of stack

#### BST - Morris Inorder Traversal

Morris Inorder Traversal run without using recursion and without extra stack space.

Morris Inorder runs in O(NlogN) time and O(1) space