heartin's blog

Create a Linked List of All Nodes at Each Level of Binary Tree Using Recursion

Problem

Given a binary tree, create a linked list of all nodes at each level of binary tree using recursion.

If there are n levels, there will be n linked lists.

You can create an ArrayList of linked lists.

 

Approach

We will create an ArrayList of linked lists. We will pass in the array list to the method along with a level attribute. 

If the size of arraylist is equal to the level, the level has not been visited before and we will create a new linked list and add elements.

Difference Between Sum of Nodes at Odd Levels and Sum of Nodes at Even Levels of a Binary Tree Using Recursion

Approach 

Recursively substract the data values of child nodes from current node.

Assume the full and complete tree with levels as:

6

11

1111

This will become 6 - (1-1-1) - (1-1-1) => 6 - (-1) - (-1) => 6+1 + 1 => 8.

 

Solution

int getLevelDiff(TreeNode n)
{
  if(n==null) return 0;
  
  return (n.data - getLevelDiff(n.left) - getLevelDiff(n.right));
}

 

Postorder Traversal Without Using Recursion With One Stack

In this solution we will be using only one stack.

 

Solution

void postorder(TreeNode n)

{

  if (n == null) return;

 

  TreeNode current = n;

  Stack s = new Stack();

  do{

  while(current!=null)

  {

    if(current.right!=null) s.push(current.right);

    s.push(current);

    current = current.left;

  }

  if(current.right ! = null && current.right == stack.peep())

  { //swap them

    stack.pop();

    stack.push(current);

Postorder Traversal Without Using Recursion With Two Stacks

Approach

We can do post order traversal iteratively using two stacks.

There are also approaches involving one stack, but this seems to be a simpler one to understand.

For a root element T1 with left child T2 and right child T3, post order traversal order will be T2, T3, and T1.

To make this happen, we should elements in the order T1, T2 and T3 into the second stack and then print them.

Approach can be summarized as:

  • Create two stacks s1 and s2.

  • Push root to first stack s1.

Preorder Traversal Without Using Recursion

Approach

  • In inorder, we print data and then go to left and right subtree.

  • We can use a stack here.

  • Every time we print a node, we will add its right and left children to the stack in order.

  • Since stack is a LIFO data structure, the left will be poped and printed first.

 

Solution

void preorder(TreeNode n)

{

  TreeNode current = n;

  Stack s = new Stack();

  s.push(current);

  while(!s.isEmpty())

Inorder Traversal Without Using Recursion

Approach

We can use a stack data structure to do this:

  • Initialize current node as root

  • Create a stack.

  • Do following until current is NULL and stack is empty:

    • Push the current node to stack and set current = current.left until current is NULL

    • If current is NULL and stack is not empty then 

      • Pop the top item from stack into current.

      • Print current,

      • Set current = current.right 

 

[Lab-Analysis] Using JAXB Annotations with SOAP Web Services

In the previous lab we created the web service with an annotation @XmlType with attribute propOrder  on top of Employee class to define order of field elements.

[Lab] Using JAXB Annotations with SOAP Web Services

We can use JAXB annoatations to specify the XML element names within the SOAP request and response.

JAXB will be making use of your default constructor and setters/getters. Remember to give a default constructor for your class in case you are having parameterized constrcutors.

 

Commonly Used JAXB 2 Annotations

In JAXB2, annotations are used both in generated Java content classes and in Java classes as input to generate schema definitions.

These binding annotations are defined in the javax.xml.bind.annotation package.

Below are some of the more commonly used annotations defined in the javax.xml.bind.annotation package.

  1. XmlAccessorType

    • Specifies the default serialization of fields and properties

    • Annotation Elements

Create a Binary Search Tree (BST) with Minimal Height from a Sorted Increasing Order Array

Problem Statement

Create a binary search tree with minimal height from a sorted increasing order array. 

 

Approach

If you traverse a Binary Search Tree in inorder traversal, you will get the numbers printed in a sorted increasing order. So you can reverse process and create a binary search tree from a sorted increasing order array of integers.

Pages

Search the Web

Custom Search

Searches whole web. Use the search in the right sidebar to search only within javajee.com!!!