Binary Trees

Binary Tree – Recursion

Recursion

• Recursion is the strategy for solving problems where a method calls itself.

• Approach
– If the problem is straightforward, solve it directly (base case – the last step to

stop the recursion).

– Else (recursive step)

  1. Simplify the problem into smaller problems.
  2. Solve the simpler problems using the same algorithm.
  3. Combine the solutions of the smaller problems that solve the general problem.

Recursion – Array Addition Example

• Given an array of [2, 3, 4, 5, 6, 7], implement a recursive method add(int[] a) that calculates the sum of all integers in the array.

• Answer:
public int add(int[] a) {

return add_helper(a, 0); //Need a helper method to access each //element

}
private int add_helper(int[] a, int index) {

if (index == a.length – 1) return a[index]; //Base case

else return a[index] + add_helper(a, ++index); //Recursive step }

Binary Tree

• Definition: Binary Tree is a data structure that has a root node and each node in the tree has at most two subtrees, which are referred to the left child and right child.

• Example:page4image1134654896

Binary Tree Traversal

• Breadth-first traversal (BFS) visits node according to how far away from the root.

• Depth-first traversal (DFS) visits nodes as far ahead as possible before backing up. There are three types of DFS for binary trees:

• Preorder traversal visits a node, then its left child, then its right child.
• Inorder traversal visits a node’s left child, then the node itself, then its right

child.
• Postorder traversal visits a node’s left child, then its right child, then itself.

Binary Tree Traversal Examplepage6image1133750048page6image1133750336

Breadth-first: Preorder: Inorder: Postorder:

Binary Tree Traversal Examplepage7image1098336496page7image1098336784

Breadth-first: 4, 3, 6, 5, 7
Preorder: 4, 3, 6, 5, 7
Inorder: 3, 4, 5, 6, 7
Postorder: 3, 5, 7, 6, 4
Visualization link: https://visualgo.net/en/bst

Which one of these is breadth-first traversal?

A. 1,2,3,4,5,6,7,8,9 B. 5,2,6,1,4,8,3,7,9 C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9page8image1097426464

Which one of these is breadth-first traversal?

A. 1,2,3,4,5,6,7,8,9

B. 5,2,6,1,4,8,3,7,9

C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9page9image1097565840

Which one of these is postorder traversal?

A. 1,3,4,2,7,9,8,6,5 B. 5,2,6,1,4,8,3,7,9 C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9page10image1098448720

Which one of these is postorder traversal?

A. 1,3,4,2,7,9,8,6,5

B. 5,2,6,1,4,8,3,7,9 C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9page11image1098511296

Which one of these is inorder traversal?

A. 1,2,3,4,5,6,7,8,9 B. 5,2,6,1,4,8,3,7,9 C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9page12image1134000496

Which one of these is inorder traversal?

A. 1,2,3,4,5,6,7,8,9

B. 5,2,6,1,4,8,3,7,9 C. 1,3,4,2,7,9,8,6,5 D. 5,3,2,4,3,6,8,7,9page13image1098532352

Which one of these is preorder traversal?

A. 1,3,4,2,7,9,8,6,5 B. 5,2,6,1,4,8,3,7,9 C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9page14image1186999744

Which one of these is preorder traversal?

A. 1,3,4,2,7,9,8,6,5

B. 5,2,1,4,3,6,8,7,9

C. 1,2,3,4,5,6,7,8,9 D. 5,3,2,4,3,6,8,7,9page15image1096445088

Tree Construction Algorithm

  1. Get the root from the pre (post) order traversal.
  2. Locate the root in the inorder traversal.
  3. Determine the sizes of your left and right subtrees from the inorder traversal, and obtain the inorder traversal of the left and right subtrees.
  4. Compute the split index of your pre (post) order traversal to get the left and right preorder traversal of your left and right subtrees.
  5. Create the root node and solve recursively for its left and right subtrees.

Binary Tree

Exercise 1: Implement findMaxSum() method that find the maximum sum of all paths (each path has their own sum and find max sum of those sums). For example, the path 1->2->5 makes the max sum of 8 and 8 is the result.

int findMaxSum(Node n) { }page17image1098569200

Binary Tree

Exercise 1: Implement findMaxSum() method that find the maximum sum of all paths (each path has their own sum and find max sum of those sums). For example, the path 1->2->5 makes sum of 8; 1->2>4 makes sum of 7; and 1->3 makes sum of 4. Therefore, 8 is the result.

int findMaxSum(Node n) {
if (n == null) return 0;

else {
int sumleft = findMaxSum(n.left);page18image1096722592

} }

int sumright = findMaxSum(n.right);
if (sumleft > sumright) return n.data + sumleft; else return n.data + sumright;

Binary Tree

• Exercise 2: Implement mirror() method that replaces the current binary tree with its own mirror version.

void mirror(Node n) { }page19image1096790224page19image1096790528page19image1096791120

Binary Tree

• Exercise 2: Implement mirror() method that replaces the current binary tree with its own mirror version.

void mirror(Node n) { if (n != null) {page20image1098676384

mirror(n.left); mirror(n.right); Node temp = n.right; n.right = n.left;
n.left = temp;page20image1098686800page20image1098687456

} }

Mobile Microservices

Let me start by stating that Microservices is NOT a pattern but rather a distinctive method of developing software systems which is becoming more and more popular as people realize the advantages of it Vs developing a Monolithic systems.

I’ve adopted and been developing & evolving this type of architecture for mobile applications and decided to share knowledge..

The core of microservices architecture is :

Smart endpoints that process info and apply logic, and dumb pipes through which the info flows.

Before we dive in to the microservices lets go through some foundational, mobile oriented paradigms.

Message-driven

Message driven architecture ( i.e. reactive ) is one of the most important paradigms one needs to understand when developing any mobile app. Most important rule of any mobile app is User Experience. A responsive system ensures quick reaction to any user requests or actions which is driven by asynchronous behavior and timely messages deliveries among objects in the system.

Lets take an example from real life:

Task in hand : Brew a pot of coffee

  • Impediments :
    • You’re out of cream and sugar.

Reactive, message driven approach:

  • Begin to brew a pot of coffee.
  • Go to the store while the coffee is brewing.
  • Buy cream and sugar.
  • Return home.
  • Drink coffee immediately.
  • Enjoy life.

react.png

Monolithic approach:

  • Go to the store.
  • Buy cream and sugar.
  • Return home.
  • Start brewing a pot of coffee.
  • Impatiently watch the pot of coffee as it brews.
  • Experience caffeine withdrawal.
  • Crash.

sequential.png

As you can clearly see, the second approach take double the time resulting in a very poor user experience.

A message-driven application may be event-driven, actor-based, or a combination of the two.

Event-driven system is based on events which are monitored by zero or more observers. This is different than imperative programming because the caller doesn’t need to block waiting for a response from the invoked routine. Events are being broadcasts and absorbed by whoever is willing to listen.

Consider the following diagram describing the event – driven architecture

eventdriven.png

Actor-based concurrency is an extension of the Event-driven system, where messages are directed to a recipient, which happens to be an actor. Messages may cross thread boundaries or be passed to another actor’s mailbox on a different physical server. This enables elasticity — scaling out on demand — as actors can be distributed across the network, yet still communicate with each other as they are all sharing the same bus.

The main difference between messages and events is that messages are directed while events happen. Messages have a clear destination while events may be observed by zero or more (0-N) observers.

 

Example of the Message driven implementation can be found at the following git repo:

Event Driven mobile foundation

Actor-based concurrency

Actor-based applications revolve around asynchronous message passing between multiple actors.

An actor is a construct with the following properties:

  • An observer for receiving messages.
  • The actor’s logic, which relies on pattern matching to determine how to handle each type of message it receives.
  • Isolated state — rather than shared state — for storing context between requests.

Actors pass messages back and forth, or to themselves. An actor can pass a message to itself in order to finish processing a long-running request after it services other messages in its queue first. A huge benefit of actor-based concurrency is that in addition to the benefits gained by an event-driven architecture, scaling computation out across network boundaries is even easier, and callback-hell is avoided because messages are directed to actors. This is a powerful concept that makes it easy to build hyper-scalable applications that are also easy to design, build, and maintain. You only need to think about how messages flow between actors.

Another major benefit of an actor-based architecture is the loose coupling of components. The caller doesn’t block a thread waiting for a response, therefore the caller can quickly move onto other work. The invoked routine, encapsulated by an actor, only needs to call the caller back if necessary.

More to come…..