In this post you can learn about binary tree common problems and their solutions in Java. You can also find interesting and elite problems solutions about Linked Lists in my previous post.

#### Short Introduction to Binary Trees.

Binary Trees are set of nodes in which one node is linked to two other nodes (left and right). Usually a reference or a pointer to topmost node is stored as a root, which can be used to traverse through all other nodes. In most cases Binary Trees are used as Binary Search Trees (BST) that have certain properties: the values in left sub tree is always smaller than or equal to its parent node's value and the values in right sub tree is always larger than its parent's value. Here is the illustration of BST. 1)Given Binary Tree, print node values in pre-order, in-order, post-order and level order.
Solution:

Unlike linear data structures such as ArrayList, LinkedList, Queue and Stack, Binary Trees can be traversad in several ways. Main traversal methods of Binary Trees are
• Pre-order - traversing starts from root and goes to left subtree then to right subtree
• In-order - traversing starts from left subtree and goes to root then to right subtree
• Post-order - traversing starts from left subtree and goes to right subtree then to root
• Level-order - traversing starts from root as level 1 and goes to every other level
Below are solution in Java for all 4 traversal methods.

2) Invert Binary Tree
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off. Here is motivation to learn how to invert Binary Tree.

Solution:
The inverse of an empty tree is the empty tree. The inverse of a tree with root r and subtrees leftb and right is a tree with root r whose right subtree is the inverse of left and whose left subtree is the inverse of right.

Time Complexity is O(n), becuase each node is vitised only once.
Space Complexity is O(n) because of recursion h (height) number of stack calls.

3) Given two binary trees, check if they are structurally identical and the nodes have the same value.

Solution:
To invert a Binary Tree, we do pre-order traverse both trees and check if values of the nodes in each tree is the same. Iterative and recursive approach can be used to solve this problem. Below I presented my recursive solution.

Time Complexity is O(n), becuase each node is vitised only once.
Space Complexity is O(n) because of recursion h (height) number of stack calls.

4) Find Lowest Common Ancestor (LCA) of a Binary Search Tree
According to WikiPedia definition , The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

Solution:
We walk down the tree as long as both p and q are in the same sub tree, in which case their values are both smaller than root's value or greater than root's value. Return when one of the p and q, are larger than root's value and the other is smaller than root's value.

Time Complexity is O(n), becuase each node is vitised only once.

5) Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Solution:
We subtract the value of current node from sum until it reaches a leaf node and the subtraction equals 0, then we can make sure there is a path. Otherwise the subtraction at the end could not be 0.