# Binary Tree Common Problems and Solutions

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.

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

Solution:

The inverse of an empty tree is the empty tree. The inverse of a tree with root

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.

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.

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.

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.

#### 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

2) Invert Binary TreeGoogle: 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**left**b 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.

#### Here are some other mostly encountered Binary Tree problems and Solutions

- Maximum Depth of Binary Tree
- Minimum Depth of Binary Tree
- Convert Sorted List to Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Check If Binary Trees are symmetric
- Flatten Binary Tree to Linked List
- Binary Tree Right Side View
- Delete Node in a BST
- Validate Binary Search Tree