Implement wildcard pattern matching with support for ‘.’ and ‘*’.
‘.’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Daily Archives: October 17, 2015
Inorder traversal using constant space – Morris Traversal
Usual approach using linear space (stack)
We can easily do the traversal by using a stack where we keep pushing left. If no left is there then we pop an element to print it and then push its right. This is O(n) time and O(n) space algorithm.
Transformation between Binary Tree and Linked Lists
Given a Binary Tree (or BST).
1. Flatten the BT into a single link in the order of inorder traversal.
2. Flatten the BT into a single link in the order of preorder traversal.
3. Flatten the BST to sorted single linked list.
4. Flatten a BST to Double Linked List
5. Flatten a BST to Circular Double Linked List
6. Convert Sorted Linked List to BST.
7. Convert heap ordered Linked List to BT.